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.

DOI: 10.4236/alamt.2015.51001                

Abstract

Newton’s iteration is a fundamental tool for numerical solutions of systems of equations. The well-known iteration  rapidly refines a crude initial approximation X₀ 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.

Keywords

Newton Iteration, Structured Matrices, Superfast Algorithm, Displacement Operators, Matrix Inverse.

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	Kailath, T. and Sayed, A. (1999) Fast Reliable Algorithms for Matrices with Structure. Society for Industrial and Applied Mathematics, Philadelphia. http://dx.doi.org/10.1137/1.9781611971354
[2]	Pan, V.Y., Branham, S., Rosholt, R. and Zheng, A. (1999) Newton’s Iteration for Structured Matrices and Linear Systems of Equations, SIAM Volume on Fast Reliable Algorithms for Matrices with Structure. Society for Industrial and Applied Mathematics, Philadelphia.
[3]	Pan, V.Y., Zheng, A.L., Huang, X.H. and Dias, O. (1997) Newton’s Iteration for Inversion of Cauchy-Like and Other Structured Matrices. Journal of Complexity, 13, 108-124. http://dx.doi.org/10.1006/jcom.1997.0431
[4]	Bini, D. and Pan, V.Y. (1994) Polynomial and Matrix Computations, Vol. 1 Fundamental Algorithms. Birkhauser, Boston.
[5]	Pan, V.Y. (2001) Structured Matrices and Polynomials: Unified Superfast Algorithms. Birkhauser, Boston.
[6]	Kailath, T., Kung, S.-Y. and Morf, M. (1979) Displacement Ranks of Matrices and Linear Equations. Journal of Mathematical Analysis and Applications, 68, 395-407. http://dx.doi.org/10.1016/0022-247X(79)90124-0
[7]	Kailath, T. and Sayed, A.H. (2002) Displacement Structure: Theory and Applications. SIAM Review, 37, 297-386. http://dx.doi.org/10.1137/1037082
[8]	Pan, V.Y. and Rami, Y. (2001) Newton’s Iteration for the Inversion of Structured Matrices. In: Bini, D., Tyrtyshnikov, E. and Yalamov, P., Eds., Structured Matrices: Recent Developments in Theory and Computation, Nova Science Publishers, New York, 79-90.
[9]	Golub, G.H. and Van Loan, C.F. (2013) Matrix Computations. 4th Edition, John Hopkins University Press, Baltimore.
[10]	Heinig, G. (1995) Inversion of Generalized Cauchy Matrices and the Other Classes of Structured Matrices. The IMA Volume in Mathematics and Its Applications, 69, 63-81.
[11]	Pan, V.Y. (1993) Decreasing the Displacement Rank of a Matrix. SIAM Journal on Matrix Analysis and Application, 14, 118-121. http://dx.doi.org/10.1137/0614010