论文标题
复杂的矩阵反转通过真实矩阵反转
Complex matrix inversion via real matrix inversions
论文作者
论文摘要
我们研究了众所周知的高斯算法的反转类似物，用于繁殖复杂矩阵。一个简单的版本是$（a + ib）^{ - 1} =（a + ba^{ - 1} b）^{ - 1} - i a^{ - 1} b（a + ba^{ - 1} b）^{ - 1} $当$ a $ a $是可逆的，可能会回到frobenius时，但已接到了frobenius，但已收到了cocant的关注。我们证明它是最佳的，需要在基地上最少的矩阵乘法和反转，我们以三种方式将其扩展：（i）到任何可逆$ a + ib $，而无需$ a $ a $ a或$ b $是可逆的； （ii）到任何迭代的二次扩展字段，$ \ mathbb {c} $上的$ \ mathbb {r} $一个特殊情况； （iii）通过利用$ a $ a $ a $ a + a + a + ba^{ - 1} b $的对称积极确定性来利用对称的正面确定性，以归功于遗传者正定矩阵$ a + ib $。我们称所有这些算法FROBENIUS倒置，我们将看到这些算法不会从Sherman-Morrison（Woodbury型身份）遵循，并且不能扩展到Moore-Penrose Pseudoinverse。我们表明，具有良好条件的真实和虚构部分的复杂矩阵可能会被任意不良条件，这是为Frobenius倒置量身定制的情况。我们证明，通过lu分解和赫尔米尼式偏移的frobenius倒置比标准反转更快，而赫尔米尼正呈正定矩阵的速度比cholesky分解的标准反转更快。我们提供了广泛的数值实验，应用Frobenius倒置以求解线性系统，评估矩阵符号函数，求解Sylvester方程并计算极性分解，表明Frobenius倒置可以比LU/Cholesky的分解更有效，而准确的损失可忽略不可损失。一个侧面结果是将高斯乘法的概括到迭代的二次扩展中，我们显示的与Karatsuba算法密切相关，用于快速整数乘法和多维快速傅立叶变换。
We study the inversion analog of the well-known Gauss algorithm for multiplying complex matrices. A simple version is $(A + iB)^{-1} = (A + BA^{-1}B)^{-1} - i A^{-1}B(A+BA^{-1} B)^{-1}$ when $A$ is invertible, which may be traced back to Frobenius but has received scant attention. We prove that it is optimal, requiring fewest matrix multiplications and inversions over the base field, and we extend it in three ways: (i) to any invertible $A + iB$ without requiring $A$ or $B$ be invertible; (ii) to any iterated quadratic extension fields, with $\mathbb{C}$ over $\mathbb{R}$ a special case; (iii) to Hermitian positive definite matrices $A + iB$ by exploiting symmetric positive definiteness of $A$ and $A + BA^{-1}B$. We call all such algorithms Frobenius inversions, which we will see do not follow from Sherman--Morrison--Woodbury type identities and cannot be extended to Moore--Penrose pseudoinverse. We show that a complex matrix with well-conditioned real and imaginary parts can be arbitrarily ill-conditioned, a situation tailor-made for Frobenius inversion. We prove that Frobenius inversion for complex matrices is faster than standard inversion by LU decomposition and Frobenius inversion for Hermitian positive definite matrices is faster than standard inversion by Cholesky decomposition. We provide extensive numerical experiments, applying Frobenius inversion to solve linear systems, evaluate matrix sign function, solve Sylvester equation, and compute polar decomposition, showing that Frobenius inversion can be more efficient than LU/Cholesky decomposition with negligible loss in accuracy. A side result is a generalization of Gauss multiplication to iterated quadratic extensions, which we show is intimately related to the Karatsuba algorithm for fast integer multiplication and multidimensional fast Fourier transform.
