算法介绍
矩阵求逆在3D程序中很常见,主要应用于求Billboard矩阵。按照定义的计算方法乘法运算,严重影响了性能。在需要大量Billboard矩阵运算时,矩阵求逆的优化能极大提高性能。这里要介绍的矩阵求逆算法称为全选主元高斯-约旦法。
高斯-约旦法(全选主元)求逆的步骤如下:
首先,对于 k 从 0 到 n - 1 作如下几步:
从第 k 行、第 k 列开始的右下角子阵中选取绝对值最大的元素,并记住次元素所在的行号和列号,在通过行交换和列交换将它交换到主元素位置上。这一步称为全选主元。
m(k, k) = 1 / m(k, k)
m(k, j) = m(k, j) * m(k, k),j = 0, 1, ..., n-1;j != k
m(i, j) = m(i, j) - m(i, k) * m(k, j),i, j = 0, 1, ..., n-1;i, j != k
m(i, k) = -m(i, k) * m(k, k),i = 0, 1, ..., n-1;i != k
最后,根据在全选主元过程中所记录的行、列交换的信息进行恢复,恢复的原则如下:在全选主元过程中,先交换的行(列)后进行恢复;原来的行(列)交换用列(行)交换来恢复。
实现(4阶矩阵)
float Inverse(CLAYMATRIX& mOut, const CLAYMATRIX& rhs){ CLAYMATRIX m(rhs); DWORD is[4]; DWORD js[4]; float fDet = 1.0f; int f = 1; for (int k = 0; k < 4; k ++) { // 第一步,全选主元 float fMax = 0.0f; for (DWORD i = k; i < 4; i ++) { for (DWORD j = k; j < 4; j ++) { const float f = Abs(m(i, j)); if (f > fMax) { fMax = f; is[k] = i; js[k] = j; } } } if (Abs(fMax) < 0.0001f) return 0; if (is[k] != k) { f = -f; swap(m(k, 0), m(is[k], 0)); swap(m(k, 1), m(is[k], 1)); swap(m(k, 2), m(is[k], 2)); swap(m(k, 3), m(is[k], 3)); } if (js[k] != k) { f = -f; swap(m(0, k), m(0, js[k])); swap(m(1, k), m(1, js[k])); swap(m(2, k), m(2, js[k])); swap(m(3, k), m(3, js[k])); } // 计算行列值 fDet *= m(k, k); // 计算逆矩阵 // 第二步 m(k, k) = 1.0f / m(k, k); // 第三步 for (DWORD j = 0; j < 4; j ++) { if (j != k) m(k, j) *= m(k, k); } // 第四步 for (DWORD i = 0; i < 4; i ++) { if (i != k) { for (j = 0; j < 4; j ++) { if (j != k) m(i, j) = m(i, j) - m(i, k) * m(k, j); } } } // 第五步 for (i = 0; i < 4; i ++) { if (i != k) m(i, k) *= -m(k, k); } } for (k = 3; k >= 0; k --) { if (js[k] != k) { swap(m(k, 0), m(js[k], 0)); swap(m(k, 1), m(js[k], 1)); swap(m(k, 2), m(js[k], 2)); swap(m(k, 3), m(js[k], 3)); } if (is[k] != k) { swap(m(0, k), m(0, is[k])); swap(m(1, k), m(1, is[k])); swap(m(2, k), m(2, is[k])); swap(m(3, k), m(3, is[k])); } } mOut = m; return fDet * f;}
比较
原算法 原算法(经过高度优化) 新算法
加法次数 103 61 39
乘法次数 170 116 69
需要额外空间 16 * sizeof(float) 34 * sizeof(float) 25 * sizeof(float)
结果不言而喻吧。
分享到:
相关推荐
[理学]大型矩阵快速求逆算法的研究.doc
矩阵求逆的快速算法.doc
(1.西北工业大学应用数学系,陕西西安710072;2.西安邮电学院应用数理系。陕西西安710121}3....文章利用分块五对角矩阵的特殊结构,给出了求分块五对角矩阵逆矩阵的快速算法,最后通过 算例来说明算法的有效性。
GPU上循环矩阵的快速求逆算法.pdf
一类广义范德蒙矩阵求逆的快速算法.docx
本文改进了求Hankel 矩阵及其逆矩阵三角分解的Chun-Kailath 快速算法,减少了该算法的计 算量,提高了精度。
matlab矩阵求逆的源码Armadillo:用于线性代数和科学计算的 C++ 库 版权所有 2008-2019 Conrad Sanderson () 版权所有 2008-2016 澳大利亚国家 ICT (NICTA) 版权所有 2017-2019 阿罗约联盟版权所有 2017-2019 Data61...
Matlab 对利用矩阵结构的快速矩阵求逆提供了很好的内置支持。 有关更多信息,请参阅“mldivide”文档的算法部分: https ://www.mathworks.com/help/matlab/ref/mldivide.html#bt4jslc-6 这里提供的函数最初是为了...
...
利用t向量来求周期三对角矩阵之逆。求逆的运算量为2n2+O(n)乘除法及n2+O(n)加减法。该算法计算量小且计算精度高。若对t向量进行截断、快速求逆,则求逆的计算量仅与n成正比。与现有快速算法相比,清除了电脑内存溢出的...
利用线性方程组是否有解给出Hankel矩阵...表明Hankel矩阵、Vandermonde 矩阵的逆矩阵可以表示为一些特殊矩阵的乘积之和,并以Hankel矩阵为例,得到了求逆的快速算法,所需计算量为O(n2),一般 n阶矩阵求逆的计算量为0(n3)。
利用Hankel矩阵的位移性质,得到了矩阵为Hankel矩阵的充要条件.从该充要条件出发,得到了求Hankel矩阵之逆矩阵的快速算法,计算复杂度为O(n2),而一般n阶矩阵求逆的复杂度为O(n2).
不是计算逆矩阵的最快方法,但可以避免完整矩阵存储的内存问题。 可选的渐进对角线计算显示。 用于快速观察对角线上的重要修改。 % Q = smartinv(N) 返回 N^-1。 N 是一个正方形对称矩阵 nx n。 % % Q = smartinv...
使其时耗严重,且其复原质量受迭代预设阈值影响较大,难以兼顾高复原质量与算法效率等不足,彻底避开迭代思想,通过引入伪逆矩阵,设计了基于非迭代伪逆矩阵的快速图像去模糊算法。通过将模糊图像分解为水平与垂直...
快速求解(单位)上下三角矩阵的逆的C++程序
但是,大规模MIMO系统中的常规线性预编码方案(例如正则归零强制(RZF)预编码)具有接近最佳的性能,但由于需要大尺寸的矩阵求逆,因此具有较高的计算复杂度。 为了解决这个问题,我们利用Cholesky分解和Sherman-...
包含《循环矩阵求逆的快速算法》、《Hankel矩阵及其逆矩阵的快速三角分解算法的改进》、《对称循环矩阵及其逆矩阵三角分解的快速算法》等论文
。。。
matlab矩阵求逆的源码Armadillo:用于线性代数和科学计算的 C++ 库 版权所有 2008-2019 Conrad Sanderson () 版权所有 2008-2016 澳大利亚国家 ICT (NICTA) 版权所有 2017-2019 阿罗约联盟版权所有 2017-2019 Data61...
一种快速的M-P逆矩阵求解算法 function Y = geninv(G) % Returns the Moore-Penrose inverse of the argument % Transpose if m < n