Geodesic
A continuation method for solving symmetric Toeplitz systems
Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 48 (2008) no. 12, pp. 2092-2106
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

A fast algorithm is proposed for solving symmetric Toeplitz systems. This algorithm continuously transforms the identity matrix into the inverse of a given Toeplitz matrix $T$. The memory requirements for the algorithm are $O(n)$, and its complexity is $O(\log n k(T)n\log n)$, where $k(T)$ is the condition number of $T$. Numerical results are presented that confirm the efficiency of the proposed algorithm. 
@article{ZVMMF_2008_48_12_a1,
     author = {M. Van Barel and Kh. D. Ikramov and A. A. Chesnokov},
     title = {A~continuation method for solving symmetric {Toeplitz} systems},
     journal = {\v{Z}urnal vy\v{c}islitelʹnoj matematiki i matemati\v{c}eskoj fiziki},
     pages = {2092--2106},
     year = {2008},
     volume = {48},
     number = {12},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZVMMF_2008_48_12_a1/}
}
TY  - JOUR
AU  - M. Van Barel
AU  - Kh. D. Ikramov
AU  - A. A. Chesnokov
TI  - A continuation method for solving symmetric Toeplitz systems
JO  - Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
PY  - 2008
SP  - 2092
EP  - 2106
VL  - 48
IS  - 12
UR  - http://geodesic.mathdoc.fr/item/ZVMMF_2008_48_12_a1/
LA  - ru
ID  - ZVMMF_2008_48_12_a1
ER  - 
%0 Journal Article
%A M. Van Barel
%A Kh. D. Ikramov
%A A. A. Chesnokov
%T A continuation method for solving symmetric Toeplitz systems
%J Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
%D 2008
%P 2092-2106
%V 48
%N 12
%U http://geodesic.mathdoc.fr/item/ZVMMF_2008_48_12_a1/
%G ru
%F ZVMMF_2008_48_12_a1
M. Van Barel; Kh. D. Ikramov; A. A. Chesnokov. A continuation method for solving symmetric Toeplitz systems. Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 48 (2008) no. 12, pp. 2092-2106. http://geodesic.mathdoc.fr/item/ZVMMF_2008_48_12_a1/

[1] Lifanov I. K., Tyrtyshnikov E. E., “Teplitsevy matritsy i singulyarnye integralnye uravneniya”, Vychisl. protsessy i sistemy, 7, Nauka, M., 1990, 94–273 | MR

[2] Prössdorf S., Silbermann B., Numerical analysis for integral and related operator equations, Akad. Verlag, Berlin, 1991 | MR | Zbl

[3] Tyrtyshnikov E. E., Teplitsevy matritsy, nekotorye ikh analogi i prilozheniya, OVM RAN, M., 1989 | MR

[4] Brent R. P., Gustavson F. G., Yun D. Y. Y., “Fast solution of Toeplitz systems of equations and computation of Padé approximants”, J. Algorithms, 1:3 (1980), 259–295 | DOI | MR | Zbl

[5] Bultheel A., Dewilde P., “On the relation between Padé approximation algorithms and Levinson Schur recursive algorithms”, Signal Processing: Theor. and Applic., 1980, 517–523 | Zbl

[6] Heinig G., Rost K., Algebraic methods for Toeplitz-like matrices and operators, Akad. Verlag, Berlin, 1984 | MR | Zbl

[7] Kailath T., Vieira A., Morf M., “Inverses of Toeplitz operators, innovations and orthogonal polynomials”, SIAM Rev., 20 (1978), 106–119 | DOI | MR

[8] Kailath T., Sayed A. H. (eds.), Fast reliable algorithms for matrices with structure, SIAM, Philadelphia, 1999 | MR

[9] Morf M., Fast algorithms for multivariable systems, Ph.D. thesis, Dep Electrical Engng, Stanford Univ., Stanford, 1974

[10] Sugiyama Y., Kasahara M., Hirasawa S., Namekawa T., “A method for colving key equation for decoding Goppa codes”, Inform. Control., 27:1 (1975), 87–99 | DOI | MR | Zbl

[11] Ammar G. S., Gragg W. B., “The generalized Schur algorithm for the superfast solution of Toeplitz systems”, Rational Approximat. and its Applic. in Math. and Phys., Lect. Notes in Math., 1237, Springer, Berlin, 1987, 315–330 | MR

[12] Van Barel M., Heinig G., Kravanja P., “A stabilized superfast solver for nonsymmetric Toeplitz systems”, SIAM J. Matrix Analys. Appl., 23:2 (2001), 494–510 | DOI | MR | Zbl

[13] de Hoog F. R., “A new algorithm for solivng Toeplitz systems of equations”, Linear Algebra Appl., 88–89 (1987), 123–138 | DOI | MR | Zbl

[14] Gemignani L., “Schur complements of Bezoutians and the inversion of block Hankel and block Toeplitz matrices”, Linear Algebra Appl., 253:1–3 (1997), 39–59 | DOI | MR | Zbl

[15] Heinig G., “Inversion of generalized Cauchy matrices and other classes of structured matrices”, Linear Algebra for Signal Proc., IMA Math. and its Applic., 69, Springer, New York, 1994, 95–114 | MR

[16] Olshevsky V., Oseledets I., Tyrtyshnikov E. E., Superfast inversion of two-level Toeplitz matrices using Newton iteration and tensor-displacement structure, Preprint, IVM RAN, M., 2006 | MR

[17] Kailath T., Kung S.-Y., Morf M., “Displacement ranks of matrices and linear equations”, J. Math. Analys. Appl., 68:2 (1979), 395–407 | DOI | MR | Zbl

[18] Codevico G., Pan V. Y., Van Barel M. etc., Newton-like iteration for general and structured matrices, Techn. Rept TW372. Dept. Computerwetenschappen, Katholieke Univ. Leuven, 2003

[19] Pan V. Y., Kinin M., Rosholt R. E., Kodal H., “Homotopic residual correction processes”, Math. Comput., 75:253 (2006), 345–368 | MR | Zbl

[20] Schultz G., “Iterative berechnung der reziproken matrix”, Z. Angew. Math. und Mech., 13 (1933), 57–59 | DOI

[21] Pan V. Y., Schreiber R., “An improved Newton iteration for the generalized inverse of a matrix, with apllications”, SIAM J. Sci. Statist. Comput., 12:5 (1991), 1109–1130 | DOI | MR | Zbl

[22] Golub G. H., Van Loan C. F., Matrix computations, Third ed., Johns Hopkins Univ. Press, Baltimore, Maryland, 1996 | MR

[23] Pan V. Y., Structured matrices and polynomials. Unified superfast algorithms, Birkhäuser, Boston; Springer, New York, 2001 | MR

[24] Dzeng D. C., Lin W.-W., “Homotopy continuation method for the numerical solutions of generalized symmetric eigenvalue problems”, J. Austral. Math. Soc. Ser. B, 32 (1991), 437–456 | DOI | MR | Zbl

[25] Allgower E. L., Georg K., Introduction to numerical continuation methods, SIAM, Philadelphia, 2003 | MR | Zbl

[26] Gunji T., Kim B. K., Kojima A., PHoM – a polyhedral homotopy continuation method for polynomial systems:, Res. Rept. B-386, Dept. of Math. and Comput. Sciences, Inst. Techn., Tokyo, 2002

[27] Schütze O., Dell'Aere A., Dellnitz M., On continuation methods for the numerical treatment of multi-objective optimization problems, IBF I, Dagstuhl, 2005

[28] Frigo M., Johnson S. G., “FFTW: An adaptive software architecture for the FFT”, Proc. IEEE Intl. Conf. on Acoustics, Speech, and Signal Proc., v. 3, Seattle, WA, 1998, 1381–1384