New Approach for the Inversion of Structured Matrices via Newton’s Iteration

作     者：Mohammad M. Tabanjeh 

作者机构：Department of Mathematics and Computer Science Virginia State University Petersburg VA USA 

出 版 物：《Advances in Linear Algebra & Matrix Theory》 (线性代数与矩阵理论研究进展（英文）)

年 卷 期：2015年第5卷第1期

页      面：1-15页

学科分类：07[理学] 0701[理学-数学] 070101[理学-基础数学] 

主　　题：Newton Iteration Structured Matrices Superfast Algorithm Displacement Operators Matrix Inverse. 

摘      要：Newton’s iteration is a fundamental tool for numerical solutions of systems of equations. The well-known iteration ?rapidly refines a crude initial approximation X0?to the inverse of a general nonsingular matrix. In this paper, we will extend and apply this method to n× n?structured matrices M?, in which matrix multiplication has a lower computational cost. These matrices can be represented by their short generators which allow faster computations based on the displacement operators tool. However, the length of the generators is tend to grow and the iterations do not preserve matrix structure. So, the main goal is to control the growth of the length of the short displacement generators so that we can operate with matrices of low rank and carry out the computations much faster. In order to achieve our goal, we will compress the computed approximations to the inverse to yield a superfast algorithm. We will describe two different compression techniques based on the SVD and substitution and we will analyze these approaches. Our main algorithm can be applied to more general classes of structured matrices.