×
Codevico, Gianni; Pan, Victor Y.; Van Barel, Marc

Newton-like iteration based on a cubic polynomial for structured matrices. (English) Zbl 1068.65050

Numer. Algorithms 36, No. 4, 365-380 (2004).
Matrices with a low displacement rank are considered. A new Newton-like iteration for computing the Moore-Penrose generalized inverses of such matrices is presented, which is based on a cubic polynomial. Numerical experiments for Toeplitz-like and Cauchy-like matrices show its efficiency and enigmatic effect of the improvement of approximation by compression in the case of structured input.
Reviewer: Oleksandr Kukush (Kyïv)

Cited in 12 Documents

MSC:

65F20 Numerical solutions to overdetermined systems, pseudoinverses
65F10 Iterative numerical methods for linear systems

Keywords:

inverse of a matrix; Moore-Penrose generalized inverse; Newton-like iteration; structured matrices; displacement structure; Toeplitz-like matrices; displacement rank; numerical experiments; Cauchy-like matrices
PDF BibTeX XML Cite
\textit{G. Codevico} et al., Numer. Algorithms 36, No. 4, 365--380 (2004; Zbl 1068.65050)
Full Text: DOI

References:

[1] G.S. Ammar and P. Gader, New decompositions of the inverse of a Toeplitz matrix, in: Signal Processing, Scattering and Operator Theory, and Numerical Methods, eds. M.A. Kaashoek, J.H. van Schuppen and A.C.N. Ran (Birkhäuser, Basel, 1990) pp. 421-428. · Zbl 0719.65020
[2] A. Ben-Israel, A note on iterative method for generalized inversion of matrices, Math. Comp. 20 (1966) 439-440. · Zbl 0142.11603
[3] A. Ben-Israel and D. Cohen, On iterative computation of generalized inverses and associated projections, SIAM J. Numer. Anal. 3 (1966) 410-419. · Zbl 0143.37402
[4] D.A. Bini, G. Codevico and M. Van Barel, Solving Toeplitz least square problems by means of Newton?s iterations, Numer. Algorithms 33 (2003) 93-103. · Zbl 1031.65059
[5] D.A. Bini and B. Meini, Solving block banded block Toeplitz systems with banded Toeplitz blocks, F.T. Luk, Proc. SPIE 3807 (1999) 300-311. · Zbl 0930.65015
[6] D.A. Bini and V.Y. Pan, Polynomial and Matrix Computations, Vol. 1: Fundamental Algorithms (Birkhäuser, Boston, 1994). · Zbl 0809.65012
[7] G. Codevico, V. Pan, M. Van Barel and X. Wang, Iterative inversion of structured matrices, Report TW351, Department of Computer Science, Katholieke Universiteit Leuven (2002); also in Special Issue on Algebraic and Numerical Algorithms of Theoret. Comput. Sci. (2004) (in press).
[8] I. Gohberg and V. Olshevsky, Circulants, displacements and decompositions of matrices, Integral Equations Operator Theory 15 (1992) 730-743. · Zbl 0772.15010
[9] I. Gohberg and A. Semencul, On the inversion of finite Toeplitz matrices and their continuous analogs, Mat. Issledovaniia 2 (1972) 187-224. · Zbl 0288.15004
[10] G.H. Golub and C.F. Van Loan, Matrix Computations, 3rd ed. (Johns Hopkins Univ. Press, Baltimore, MD, 1996). · Zbl 0865.65009
[11] G. Heinig and K. Rost, Algebraic Methods for Toeplitz-like Matrices and Operators (Akademie-Verlag, Berlin, and Birkhäuser, Basel/Stuttgart, 1984). · Zbl 0549.15013
[12] T. Kailath, S.-Y. Kung and M. Morf, Displacement ranks of matrices and linear equations, J. Math. Anal. Appl. 68 (1979) 395-407. · Zbl 0433.15001
[13] T. Kailath, S. Kung and M. Morf, Displacement ranks of a matrix, Bull. Amer. Math. Soc. 1 (1979) 769-773. · Zbl 0417.65015
[14] T. Kailath and A. Sayed, Displacement structure: Theory and applications, SIAM Rev. 37(3) (1995) 297-386. · Zbl 0839.65028
[15] T. Kailath and A.H. Sayed, eds., Fast Reliable Algorithms for Matrices with Structure (SIAM, Philadelphia, PA, 1999). · Zbl 0931.65018
[16] T. Kailath, A. Vieira and M. Morf, Inverses of Toeplitz operators, innovations and orthogonal polynomials, SIAM Rev. 20 (1978) 106-119. · Zbl 0382.47013
[17] M. Morf, Fast algorithms for multivariable systems, Ph.D. thesis, Department of Electrical Engineering, Stanford University, Stanford, CA (1974). · Zbl 0317.62067
[18] V.Y. Pan, Nearly optimal computations with structured matrices, in: Proc. of the 11th Annual ACM?SIAM Symposium on Discrete Algorithms (SODA?2000) (ACM/SIAM, New York, Philadephia, PA, 2000) pp. 953-962. · Zbl 0953.65030
[19] V.Y. Pan, Structured Matrices and Polynomials: Unified Superfast Algorithms (Birkhäuser/Springer, Boston/New York, 2001). · Zbl 0996.65028
[20] V.Y. Pan, M. Kunin, R.E. Rosholt and H. Cebecio?lu, Residual correction algorithms for general and structured matrices, Preprint (2002).
[21] V.Y. Pan and R. Schreiber, An improved Newton iteration for the generalized inverse of a matrix, with applications, SIAM J. Sci. Statist. Comput. 12(5) (1991) 1109-1131. · Zbl 0733.65023
[22] V.Y. Pan and X. Wang, Inversion of displacement operators, SIAM J. Matrix Anal. Appl. 24(3) (2003) 660-677. · Zbl 1056.47015
[23] G. Schultz, Iterative Berechnung der Reciproken Matrix, Z. Angew. Math. Mech. 13 (1933) 57-59. · JFM 59.0535.04
[24] T. Söderström and G.W. Stewart, On the numerical properties of an iterative method for computing the Moore?Penrose generalized inverse, SIAM J. Numer. Anal. 11 (1974) 61-74. · Zbl 0273.65028
[25] M. Van Barel and G. Codevico, An adaptation of the Newton iteration method to solve symmetric positive definite Toeplitz systems, Report TW349, Department of Computer Science, Katholieke Universiteit Leuven (2002).
[26] Y. Wei, J. Cai and M. Ng, Computing Moore?Penrose inverses of Toeplitz matrices by Newton?s iteration, Math. Comput. Model., to appear. · Zbl 1069.65045
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.