一种基于FPGA的非奇异矩阵快速求逆方法

摘要

本发明公开了一种基于FPGA的非奇异矩阵快速求逆方法，采用元素重新排序的改进Gauss‑Jordan消去法，克服了矩阵必须是正定矩阵的要求，实现了对非奇异矩阵的求逆。本发明根据改进的Gauss‑Jordan消去法推导出来矩阵求逆的迭代公式，然后将矩阵求逆的公式转换成适合FPGA快速处理的并行流水线形式。对于N维的矩阵，需要进行相同的N次消去迭代运算。每次消去迭代运算分块进行计算，同时完成矩阵元素的重新排序。本发明仅需要一个除法器，N‑1个乘法器和N‑1个加法器即可完成非奇异矩阵的求逆运算，适用范围广，实现简单，处理速度快，非常适合工程应用。

说明书

技术领域

本发明涉及矩阵运算技术领域，尤其涉及一种基于FPGA的非奇异矩阵快速求逆方法。

背景技术

矩阵运算特别是矩阵求逆在实际工程应用中站有很重要的地位，随着网络通信、人工智能、大数据处理等技术的发展，对矩阵求逆运算的要求也越来越高。目前矩阵求逆的方法大多都要求矩阵是正定的，对不是正定的其它非奇异矩阵无能为力。有的矩阵求逆方法虽然可以处理非奇异矩阵，但是运算复杂，而且要求矩阵的维数必须是2

发明内容

针对现有技术的不足，本发明提出如下技术方案：

一种基于FPGA的非奇异矩阵快速求逆方法，非奇异矩阵为N维，表示为A，经过N次步骤相同的消去运算，得到逆矩阵A

(1)将A分成4个矩阵块A

(2)将所述矩阵块A

(3)将所述矩阵块A

(4)将所述矩阵块A

(5)将所述矩阵块A

(6)用所述矩阵B更新所述矩阵A，重复所述步骤(1)～(5)，直到迭代次数大于N，完成所述N维非奇异矩阵A的求逆。

进一步地，所述步骤(4)具体通过以下子步骤实现：

(4.1)计算所述矩阵块A

(4.2)计算所述矩阵块B

(4.3)重复步骤(4.1)和(4,2)，直到j＞N，结束循环，得到矩阵块B

进一步地，所述步骤(2)使用一个除法器，被除数是常数1，除数是元素a

进一步地，所述步骤(4.1)复用步骤(3)中的N-1个乘法器，同时将所述矩阵块A

进一步地，所述步骤(3)中，所述存放到矩阵块B

进一步地，所述步骤(5)中，所述存放到矩阵块B

进一步地，所述矩阵块B

进一步地，所述矩阵A完成一次消去运算的表达式如下：

进一步地，所述每一次的消去运算均采用如下分块矩阵的形式表示：

其中，

本发明的有益效果是：

本发明将求逆矩阵的范围由正定矩阵扩展为非奇异矩阵，同时根据推导的矩阵求逆的消去运算公式，结合FPGA的并行流水线操作，减少了运算的复杂度，提高了矩阵求逆的速度。

附图说明

图1是本发明的矩阵求逆流程图。

具体实施方式

下面根据附图和优选实施例详细描述本发明，本发明的目的和效果将变得更加明白，以下结合附图和实施例，对本发明进行进一步详细说明。应当理解，此处所描述的具体实施例仅仅用以解释本发明，并不用于限定本发明。

一种基于FPGA的非奇异矩阵快速求逆方法，根据元素重新排序的Gauss-Jordan消去法，推导出矩阵求逆的迭代的公式，推导过程如下：

对于n维的非奇异矩阵A，首先构造增广矩阵，表示如下：

对增广矩阵的前n列采用Gauss-Jordan消去法进行一步消去运算，消去运算的步骤如下：首先对矩阵的第一行元素进行初等变换，将所有元素乘以1/a

其中，新的变量计算公式如下：

直接采用Gauss-Jordan消去法，程序设计比较繁琐，本发明采用重新排序的Gauss-Jordan消去法进行程序的设计，完成首次的一步消去运算后，将(2)中增广矩阵的首行元素通过初等变换交换到矩阵的最后一行，更新如下：

更新后的每一步变量的计算公式如下：

对更新后增广矩阵的第2到第n+1列进行和首次相同的一步消去运行。以此类推，对更新增广矩阵的第c到n+c-1列进行第c次一步消去运算，c＝1,2,…,n。完成c步消去运算后，增广矩阵的前n列化简成为单位矩阵，增广矩阵的后n列是矩阵A的逆矩阵，如下所示：

采用重新排序的Gauss-Jordan消去法，每一步的消去运算都是相同的，适合程序实现，对于每一步的Gauss-Jordan消去运算，可以采用如下分块矩阵的形式表示：

每个分块矩阵的运算公式如下：

由上面的推导可以看出，重新排序的Gauss-Jordan消去法的所有运算都是矩阵的初等变换，所以对于非奇异的矩阵，通过重新排序的Gauss-Jordan消去法都可以求出逆矩阵。

如图1所示，将矩阵求逆的公式转换成适合FPGA快速处理的并行流水线形式，对于N维的非奇异矩阵A，进行N次步骤相同的消去迭代运算，具体步骤如下：

步骤一：将消去迭代运算前矩阵A和消去迭代后矩阵B分别分成4个矩阵块，同时完成矩阵元素的重新排序。消去迭代运算前矩阵A分成4个矩阵块，其中A

步骤二：计算消去迭代运算后矩阵块B

步骤三：计算消去迭代运算后矩阵块B

步骤四：计算消去迭代运算后矩阵块B

步骤四的迭代计数器为j时的迭代运算通过以下子步骤来实现：

(4.1)计算A

(4.2)计算消去迭代运算后矩阵块B

矩阵块B

步骤五：计算消去迭代运算后矩阵块B

步骤六：用矩阵B来更新矩阵A，然后重复步骤一到步骤五，直到迭代次数大于N，完成非奇异矩阵A的求逆。

本发明的矩阵求逆运算中，充分利用了FPGA的并行流水线操作加快了迭代运算。FPGA中除法器、乘法器和加法器是可以并行计算的，首次消去迭代的步骤四的(4.1)完成元素b

步骤四中矩阵块B

如果FPGA不采用并行流水线操作，本发明求逆方法的时间复杂度是O(N

本领域普通技术人员可以理解，以上所述仅为发明的优选实例而已，并不用于限制发明，尽管参照前述实例对发明进行了详细的说明，对于本领域的技术人员来说，其依然可以对前述各实例记载的技术方案进行修改，或者对其中部分技术特征进行等同替换。凡在发明的精神和原则之内，所做的修改、等同替换等均应包含在发明的保护范围之内。