×

A fast solver for linear systems with displacement structure. (English) Zbl 1203.65062

Summary: We describe a fast solver for linear systems with reconstructible Cauchy-like structure, which requires \(O(rn^{2})\) floating point operations and \(O(rn)\) memory locations, where \(n\) is the size of the matrix and \(r\) its displacement rank. The solver is based on the application of the generalized Schur algorithm to a suitable augmented matrix, under some assumptions on the knots of the Cauchy-like matrix. It includes various pivoting strategies, already discussed in the literature, and a new algorithm, which only requires reconstructibility. We have developed a software package, written in Matlab and C-MEX, which provides a robust implementation of the above method. Our package also includes solvers for Toeplitz(+Hankel)-like and Vandermonde-like linear systems, as these structures can be reduced to Cauchy-like by fast and stable transforms. Numerical experiments demonstrate the effectiveness of the software.

MSC:

65F05 Direct numerical methods for linear systems and matrix inversion
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Ammar, G.S., Gragg, W.B.: Superfast solution of real positive definite Toeplitz systems. SIAM J. Matrix Anal. Appl. 9(1), 61–76 (1988) · Zbl 0658.65022
[2] Anderson, E., Bai, Z., Bischof, C., Demmel, J., Dongarra, J., Du Croz, J., Greenbaum, A., Hammarling, S., McKenney, A., Ostrouchov, S., Sorensen, D.: LAPACK Users’ Guide. SIAM, Philadelphia (1992) · Zbl 0843.65018
[3] Aricò, A., Rodriguez, G.: toms729gw: a Matlab (Fortran) MEX Gateway for TOMS Algorithm 729, by P. C. Hansen and T. Chan. University of Cagliari (2008). Available at: http://bugs.unica.it/\(\sim\)gppe/soft/
[4] Arushanian, O.B., Samarin, M.K., Voevodin, V.V., Tyrtyshnikov, E., Garbow, B.S., Boyle, J.M., Cowell, W.R., Dritz, K.W.: The TOEPLITZ Package Users’ Guide. Technical Report ANL-83-16, Argonne National Laboratory (1983)
[5] Bartels, R.H., Golub, G.H., Saunders, M.A.: Numerical techniques in mathematical programming. In: Nonlinear Programming (Proc. Sympos., Univ. of Wisconsin, Madison, Wis., 1970), pp. 123–176. Academic, New York (1970) · Zbl 0228.90030
[6] Bini, D.A., Boito, P.: A fast algorithm for approximate polynomial gcd based on structured matrix computations. In: Bini, D.A., Mehrmann, V., Olshevsky, V., Tyrtyshnikov, E., Van Barel, M. (eds.) Numerical Methods for Structured Matrices and Applications: The Georg Heinig Memorial Volume. Operator Theory: Advances and Applications, vol. 199, pp. 155–173. Birkhäuser, Basel (2010)
[7] Björck, Å.: Pivoting and stability in the augmented system method. In: Numerical Analysis 1991 (Dundee, 1991). Pitman Res. Notes Math. Ser., vol. 260, pp. 1–16. Longman Sci. Tech., Harlow (1992) · Zbl 0796.65056
[8] Blackford, L.S., Demmel, J., Dongarra, J., Duff, I., Hammarling, S., Henry, G., Heroux, M., Kaufman, L.: An updated set of basic linear algebra subprograms (BLAS). ACM Trans. Math. Softw. 28(2), 135–151 (2002) · Zbl 1070.65520
[9] Calvetti, D., Reichel, L.: Factorizations of Cauchy matrices. J. Comput. Appl. Math. 86(1), 103–123 (1997) · Zbl 0891.65023
[10] Chandrasekaran, S., Gu, M., Sun, X., Xia, J., Zhu, J.: A superfast algorithm for Toeplitz systems of linear equations. SIAM J. Matrix Anal. Appl. 29(4), 1247–1266 (2007) · Zbl 1221.65084
[11] Chun, J., Kailath, T.: Divide-and-conquer solutions of least-squares problems for matrices with displacement structure. SIAM J. Matrix Anal. Appl. 12(1), 128–145 (1991) · Zbl 0718.65031
[12] Codevico, G., Heinig, G., Van Barel, M.: A superfast solver for real symmetric Toeplitz systems using real trigonometric transformations. Numer. Linear Algebra Appl. 12(8), 699–713 (2005) · Zbl 1164.65334
[13] Friedlander, B., Morf, M., Kailath, T., Ljung, L.: New inversion formulas for matrices classified in terms of their distance from Toeplitz matrices. Linear Algebra Appl. 27, 31–60 (1979) · Zbl 0414.15005
[14] Gohberg, I., Kailath, T., Olshevsky, V.: Fast Gaussian elimination with partial pivoting for matrices with displacement structure. Math. Comput. 64(212), 1557–1576 (1995) · Zbl 0848.65010
[15] Graillat, S., Ménissier-Morain, V.: Error-free transformations in real and complex floating point arithmetic. In: Proceedings of the International Symposium on Nonlinear Theory and its Applications, pp. 341–344. Vancouver, Canada (2007)
[16] Gu, M.: Stable and efficient algorithms for structured systems of linear equations. SIAM J. Matrix Anal. Appl. 19(2), 279–306 (1998) · Zbl 0915.65024
[17] Hansen, P.C., Chan, T.F.: Fortran subroutines for general Toeplitz systems. ACM Trans. Math. Softw. 18(3), 256–273 (1992) · Zbl 0894.65010
[18] Heinig, G.: Inversion of generalized Cauchy matrices and other classes of structured matrices. In: Linear Algebra for Signal Processing (Minneapolis, MN, 1992). IMA Vol. Math. Appl., vol. 69, pp. 63–81. Springer, New York (1995) · Zbl 0823.65020
[19] Heinig, G., Bojanczyk, A.: Transformation techniques for Toeplitz and Toeplitz-plus-Hankel matrices. I. Transformations. Linear Algebra Appl. 254, 193–226 (1997) · Zbl 0872.65021
[20] Heinig, G., Bojanczyk, A.: Transformation techniques for Toeplitz and Toeplitz-plus-Hankel matrices. II. Algorithms. Linear Algebra Appl. 278(1–3), 11–36 (1998) · Zbl 0939.65039
[21] Heinig, G., Rost, K.: Algebraic Methods for Toeplitz-Like Matrices and Operators. Operator Theory: Advances and Applications, vol. 13. Birkhäuser, Basel (1984) · Zbl 0549.15013
[22] Higham, N.J.: Accuracy and Stability of Numerical Algorithms, 2nd edn. SIAM, Philadelphia (2002) · Zbl 1011.65010
[23] Kahan, W.: Lecture notes on the status of IEEE standard 754 for binary floating-point arithmetic. Available at: http://www.cs.berkeley.edu/\(\sim\)wkahan/ieee754status/IEEE754.PDF (1996)
[24] Kailath, T., Chun, J.: Generalized displacement structure for block-Toeplitz, Toeplitz-block, and Toeplitz-derived matrices. SIAM J. Matrix Anal. Appl. 15(1), 114–128 (1994) · Zbl 0797.65021
[25] Kailath, T., Kung, S.Y., Morf, M.: Displacement ranks of matrices and linear equations. J. Math. Anal. Appl. 68(2), 395–407 (1979) · Zbl 0433.15001
[26] Kailath, T., Sayed, A.H.: Displacement structure: theory and applications. SIAM Rev. 37(3), 297–386 (1995) · Zbl 0839.65028
[27] Kailath, T., Sayed, A.H., (eds.): Fast Reliable Algorithms for Matrices with Structure. Society for Industrial and Applied Mathematics (SIAM). Philadelphia, PA (1999) · Zbl 0931.65018
[28] Katholieke Universiteit Leuven, Department of Computer Science. MaSe-Team (Matrices having Structure) (2010). Available at: http://www.cs.kuleuven.ac.be/\(\sim\)marc/software/
[29] The MathWorks, Natick. Matlab ver. 7.9 (2009)
[30] van der Mee, C.V.M., Seatzu, S.: A method for generating infinite positive self-adjoint test matrices and Riesz bases. SIAM J. Matrix Anal. Appl. 26(4), 1132–1149 (2005) · Zbl 1114.42014
[31] Poloni, F.: A note on the O(n)-storage implementation of the GKO algorithm and its adaptation to Trummer-like matrices. Numer. Algorithms (2010). doi: 10.1007/s11075-010-9361-5 · Zbl 1195.65057
[32] Rodriguez, G.: Fast solution of Toeplitz- and Cauchy-like least-squares problems. SIAM J. Matrix Anal. Appl. 28(3), 724–748 (2006, electronic) · Zbl 1157.65355
[33] Siegel, I.H.: Deferment of computation in the method of least squares. Math. Comput. 19, 329–331 (1965) · Zbl 0143.17201
[34] Stewart, M.: A superfast Toeplitz solver with improved numerical stability. SIAM J. Matrix Anal. Appl. 25(3), 669–693 (2003, electronic) · Zbl 1061.65025
[35] Sweet, D.R., Brent, R.P.: Error analysis of a fast partial pivoting method for structured matrices. In: Luk, F.T. (ed.) Advanced Signal Processing Algorithms, vol. 2563, pp. 266–280. SPIE, San Diego (1995)
[36] University of Pisa, Department of Mathematics. Structured matrix analysis: numerical methods and applications (2010). Available at: http://bezout.dm.unipi.it/
[37] Van Barel, M., Heinig, G., Kravanja, P.: A stabilized superfast solver for nonsymmetric Toeplitz systems. SIAM J. Matrix Anal. Appl. 23(2), 494–510 (2001, electronic) · Zbl 1002.65033
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.