×

Superfast algorithms for Cauchy-like matrix computations and extensions. (English) Zbl 0971.65024

The algorithm by M. Morf [Doubling algorithms for Toeplitz and related equations, in: Proc. IEEE Int. Conf. on ASSP, IEEE Computer Soc. Press, Silvert Spring, MD, 954-959 (1980)] and by R. R. Bitmead and B. D. D. Anderson [ibid. 34, 103-116 (1980; Zbl 0458.65018)] to solve Toeplitz and Toeplitz-like systems is based on the notion of displacement rank and a divide and conquer strategy. In combination with the fast Fourier transform (FFT), this gives superfast algorithms that solve a system of size \(n\) in \(O(n\log^2 n)\) operations.
In this paper, the authors develop a similar strategy for Cauchy (displacement rank 1) and Cauchy-like (displacement rank \(r\)) matrices. Here the displacement rank is with respect to the displacement operator \(\nabla A = D(q)A-AD(t)\) where \(D(q)\) and \(D(t)\) are diagonal matrices. Because matrix vector multiplications for these matrices can not be directly computed with FFT, the resulting algorithm has a complexity of \(O(nr^2\log^3n)\).
In principle the algorithm works for strongly nonsingular matrices \(A\), but a technique of symmetrization and/or randomization can overcome this restriction. As by-products algorithms for determinant calculation, triangular factorization, least squares solution, and matrix inversion are obtained. The algorithms apply to matrices with entries from an arbitrary field. Comparison with other (super)fast algorithms for such matrices is also made.

MSC:

65F05 Direct numerical methods for linear systems and matrix inversion
65F20 Numerical solutions to overdetermined systems, pseudoinverses
65Y20 Complexity and performance of numerical algorithms
65F40 Numerical computation of determinants

Citations:

Zbl 0458.65018
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bitmead, R. R.; Anderson, B. D.O., Asymptotically fast solution of Toeplitz and related systems of linear equations, Linear Algebra Appl., 34, 103-116 (1980) · Zbl 0458.65018
[2] J.A. Ball, I. Gohberg, L. Rodman, Interpolation of Rational Matrix Functions, OT45, Birkhäuser, Basel, 1990; J.A. Ball, I. Gohberg, L. Rodman, Interpolation of Rational Matrix Functions, OT45, Birkhäuser, Basel, 1990 · Zbl 0708.15011
[3] D. Bini, V.Y. Pan, Polynomial and Matrix Computations, Volume 1: Fundamental Algorithms, Birkhäuser, Boston, 1994; D. Bini, V.Y. Pan, Polynomial and Matrix Computations, Volume 1: Fundamental Algorithms, Birkhäuser, Boston, 1994
[4] Björck, A.; Pereyra, V., Solution of Vandermonde systems of equations, Math. Comp., 24, 893-903 (1970) · Zbl 0221.65054
[5] Cauchy, A. L., Mémorie sur les fonctions alternées et sur les somme alternées, Exercises d’ Analyse et de Phys. Math., II, 151-159 (1841)
[6] Cantor, D. G.; Kaltofen, E., On fast multiplication of polynomials over arbitrary rings, Acta Inf., 28, 7, 697-701 (1991) · Zbl 0766.68055
[7] J.F. Canny, E. Kaltofen, Y. Lakshman, Solving systems of non-linear polynomial equations faster, Proc. ACM-SIGSAM Int. Symp. on Symb. and Alg. Comp. (ISSAC’89), ACM Press, New York, 1989, pp. 121-128; J.F. Canny, E. Kaltofen, Y. Lakshman, Solving systems of non-linear polynomial equations faster, Proc. ACM-SIGSAM Int. Symp. on Symb. and Alg. Comp. (ISSAC’89), ACM Press, New York, 1989, pp. 121-128
[8] Donoghue, W. F., Monotone Matrix Functions and Analytic Continuation (1974), Springer: Springer Berlin · Zbl 0278.30004
[9] Demillo, R. A.; Lipton, R. J., A probabilistic remark on algebraic program testing, Inform. Process. Lett., 7, 4, 193-195 (1978) · Zbl 0397.68011
[10] Fink, T.; Heinig, G.; Rost, K., An inversion formula and fast algorithm for Cauchy-Vandermonde matrices, Linear Algebra Appl., 183, 179-191 (1993) · Zbl 0776.65019
[11] Gautschi, W., Norm estimates for the inverses of Vandermonde matrices, Numer. Math., 23, 337-347 (1975) · Zbl 0304.65031
[12] W. Gautschi, How (un)stable are Vandermonde systems? in: R. Wong (Ed.), Proceedings of the International Symposium on Asymptotic and Computational Analysis: Conference in Honor Frank W.J. Olver’s 65th Birthday. Lecture Notes in Pure and Applied Mathematics, vol. 124, Marcel-Decker, New York, pp. 193-210; W. Gautschi, How (un)stable are Vandermonde systems? in: R. Wong (Ed.), Proceedings of the International Symposium on Asymptotic and Computational Analysis: Conference in Honor Frank W.J. Olver’s 65th Birthday. Lecture Notes in Pure and Applied Mathematics, vol. 124, Marcel-Decker, New York, pp. 193-210
[13] Gastinel, N., Inversion d’une matrice generalisant la matrice de Hilbert, Chiffres, 3, 149-152 (1960) · Zbl 0213.16303
[14] Gerasoulis, A., A fast algorithm for the multiplication of generalized Hilbert matrices with vectors, Math. Comp., 50, 181, 179-188 (1987) · Zbl 0648.65040
[15] Gohberg, I.; Kailath, T.; Koltracht, I., Efficient solution of linear systems of equations with recursive structure, Linear Algebra Appl., 80, 81-113 (1986) · Zbl 0627.65025
[16] Gohberg, I.; Kailath, T.; Koltracht, I.; Lancaster, P., Linear complexity parallel algorithms for linear systems of equations with recursive structure, Linear Algebra Appl., 88/89, 271-315 (1987) · Zbl 0624.65020
[17] Gohberg, I.; Kailath, T.; Olshevsky, V., Fast Gausian elimination with partial pivoting for matrices with displacement structure, Math. Comp., 64, 1557-1576 (1995) · Zbl 0848.65010
[18] G.H. Golub, C.F. Van Loan, Matrix Computations, Johns Hopkins University Press, Baltimore, MD, 1989 (second ed.), 1996 (third ed.); G.H. Golub, C.F. Van Loan, Matrix Computations, Johns Hopkins University Press, Baltimore, MD, 1989 (second ed.), 1996 (third ed.) · Zbl 0733.65016
[19] Gohberg, I.; Olshevsky, V., Complexity of multiplication with vectors for structured matrices, Linear Algebra Appl., 202, 163-192 (1994) · Zbl 0803.65053
[20] Gohberg, I.; Olshevsky, V., Fast algorithms with preprocessing for matrix-vector multiplication problems, J. Complexity, 10, 4, 411-427 (1994) · Zbl 0820.68051
[21] Gohberg, I.; Olshevsky, V., Fast state space algorithms for matrix Nehari and Nehari-Takagi interpolation problems, Integral Equations Operator Theory, 20, 1, 44-83 (1994) · Zbl 0808.47014
[22] I. Gohberg, V. Olshevsky, Fast inversion of Vandermonde and Vandermonde-like matrices, in: A. Paulraj, V. Roychowdhury, C. Shaper (Eds.), Communications, Computation, Control and Signal Processing: A Tribute to Thomas Kailath, Kluwer Academic Publisher, Dordrecht, 1996, pp. 205-221; I. Gohberg, V. Olshevsky, Fast inversion of Vandermonde and Vandermonde-like matrices, in: A. Paulraj, V. Roychowdhury, C. Shaper (Eds.), Communications, Computation, Control and Signal Processing: A Tribute to Thomas Kailath, Kluwer Academic Publisher, Dordrecht, 1996, pp. 205-221
[23] Greengard, L.; Rokhlin, V., A fast algorithm for particle simulation, J. Comput. Phys., 73, 2, 325-348 (1987) · Zbl 0629.65005
[24] Higham, N. J., Fast solution of Vandermonde-like systems involving orthogonal polynomials, IMAJ. Numer. Anal., 8, 473-486 (1988) · Zbl 0666.65025
[25] Higham, N. J., Stability analysis of algorithm for solving confluent Vandermonde-like systems, SIAM J. Matrix Anal. Appl., 11, 23-41 (1990) · Zbl 0724.65025
[26] G.Heinig,InversionofgeneralizedCauchymatricesandtheotherclassesofstructuredmatrices,LinearAlgebraforSignalProcessing,IMAVolumeinMathematicsanditsApplications,vol.69, Springer, Berlin, 1995, pp. 95-114; G.Heinig,InversionofgeneralizedCauchymatricesandtheotherclassesofstructuredmatrices,LinearAlgebraforSignalProcessing,IMAVolumeinMathematicsanditsApplications,vol.69, Springer, Berlin, 1995, pp. 95-114
[27] H. Heinig, K. Rost, Algebraic methods for Toeplitz-like matrices and operators, Operator Theory, vol. 13, Birkhäuser, Basel, 1984; H. Heinig, K. Rost, Algebraic methods for Toeplitz-like matrices and operators, Operator Theory, vol. 13, Birkhäuser, Basel, 1984 · Zbl 0549.15013
[28] E. Kaltofen, Asymptotically fast solution of Toeplitz-like singular linear systems, Proc. ACM-SIGSAM Intern. Symp. on Symbolic and Alg. Comp., ACM Press, New York, 1994, pp. 297-304; E. Kaltofen, Asymptotically fast solution of Toeplitz-like singular linear systems, Proc. ACM-SIGSAM Intern. Symp. on Symbolic and Alg. Comp., ACM Press, New York, 1994, pp. 297-304 · Zbl 0978.15500
[29] Kaltofen, E., Analysis of Coppersmith’s block Wiedemann algorithm for the parallel solution of sparse linear systems, Math. Comp., 64, 210, 777-806 (1995) · Zbl 0828.65035
[30] 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
[31] E. Kaltofen, B.D. Saunders, On Wiedemann’s method for solving sparse linear systems, Proc. AAECC-5, Lecture Notes in Computer Science, vol. 536, Springer, Berlin, 1991, pp. 29-38; E. Kaltofen, B.D. Saunders, On Wiedemann’s method for solving sparse linear systems, Proc. AAECC-5, Lecture Notes in Computer Science, vol. 536, Springer, Berlin, 1991, pp. 29-38 · Zbl 0778.65034
[32] Lu, H., Fast solution of confluent Vandermonde linear systems, SIAM J. Matrix Anal. Appl., 15, 4, 1277-1289 (1994) · Zbl 0806.65021
[33] Lu, H., Fast algorithms for confluent Vandermonde linear systems and generalized Trummer’s problem, SIAM J. Matrix Anal. Appl., 16, 2, 655-674 (1995) · Zbl 0823.65022
[34] Lu, H., Solution of Vandermonde-like systems and confluent Vandermonde-like systems, SIAMJ. Matrix Anal. Appl., 17, 1, 127-138 (1996) · Zbl 0842.65013
[35] M. Morf, Fast algorithms for multivariable systems, Ph.D. Thesis, Department of Electrical Engineering, Stanford University, Stanford, CA, 1974; M. Morf, Fast algorithms for multivariable systems, Ph.D. Thesis, Department of Electrical Engineering, Stanford University, Stanford, CA, 1974
[36] B. Mourrain, V.Y. Pan, Multivariate polynomials, duality and structured matrices, J. Complexity 16 (1) 2000; B. Mourrain, V.Y. Pan, Multivariate polynomials, duality and structured matrices, J. Complexity 16 (1) 2000 · Zbl 0963.68232
[37] M. Morf, Doubling algorithms for Toeplitz and related equations, in: Proceedings of the IEEE International Conference on ASSP, IEEE Computer Society Press, Silver Spring, MD, 1980, pp. 954-959; M. Morf, Doubling algorithms for Toeplitz and related equations, in: Proceedings of the IEEE International Conference on ASSP, IEEE Computer Society Press, Silver Spring, MD, 1980, pp. 954-959
[38] V. Olshevsky, V.Y. Pan, A unified superfast algorithm for boundary rational tangential interpolation problem and for inversion and factorization of dense structured matrices, in: Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society Press, Silver Spring, MD, October 1998, pp. 192-201; V. Olshevsky, V.Y. Pan, A unified superfast algorithm for boundary rational tangential interpolation problem and for inversion and factorization of dense structured matrices, in: Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society Press, Silver Spring, MD, October 1998, pp. 192-201
[39] V. Olshevsky, V.Y. Pan, Polynomial and rational interpolation and multipoint evaluation (with structured matrices), in: Proceedings of the 26th International Colloquium on Automata, Languages and Programming (ICALP’99), Lecture Notes in Computer Science, vol. 1644, Springer, Berlin, 1999, pp. 585-594; V. Olshevsky, V.Y. Pan, Polynomial and rational interpolation and multipoint evaluation (with structured matrices), in: Proceedings of the 26th International Colloquium on Automata, Languages and Programming (ICALP’99), Lecture Notes in Computer Science, vol. 1644, Springer, Berlin, 1999, pp. 585-594 · Zbl 0937.65010
[40] V. Olshevsky, M.A. Shokrollahi, A displacement approach to efficient decoding of algebraic-geometric codes, in: Proceedings of the 31st Annual Symposium on Theory of Computing, ACM Press, New York, May 1999, 235-244; V. Olshevsky, M.A. Shokrollahi, A displacement approach to efficient decoding of algebraic-geometric codes, in: Proceedings of the 31st Annual Symposium on Theory of Computing, ACM Press, New York, May 1999, 235-244 · Zbl 1345.94104
[41] V.Y. Pan, On computations with dense structured matrices, Proc. ACM-SIGSAM Intern. Symp. on Symbolic and Alg. Comp., ACM Press, New York, 1989, pp. 34-42. Math. Comp. 55 (191) (1990) 179-190; V.Y. Pan, On computations with dense structured matrices, Proc. ACM-SIGSAM Intern. Symp. on Symbolic and Alg. Comp., ACM Press, New York, 1989, pp. 34-42. Math. Comp. 55 (191) (1990) 179-190
[42] V.Y.Pan,ParametrizationofNewton’siterationforcomputationswithstructuredmatricesandapplications, Comput. Math. (with Appl.) 24 (3) (1992) 61-75; V.Y.Pan,ParametrizationofNewton’siterationforcomputationswithstructuredmatricesandapplications, Comput. Math. (with Appl.) 24 (3) (1992) 61-75
[43] Pan, V. Y., Decreasing the displacement rank of a matrix, SIAM J. Matrix Anal. Appl., 14, 1, 118-121 (1993) · Zbl 0772.15012
[44] V.Y. Pan, A unified superfast divide-and-conquer algorithm for structured matrices, MSRI Preprint 1999-033, Mathematical Sciences Research Institute, Berkeley, CA, April 1999; V.Y. Pan, A unified superfast divide-and-conquer algorithm for structured matrices, MSRI Preprint 1999-033, Mathematical Sciences Research Institute, Berkeley, CA, April 1999
[45] V.Y. Pan, Nearly optimal computations with structured matrices, in: Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’2000), ACM Press, New York, and SIAM Publications, Philadelphia, PA, 2000, pp. 953-962; V.Y. Pan, Nearly optimal computations with structured matrices, in: Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’2000), ACM Press, New York, and SIAM Publications, Philadelphia, PA, 2000, pp. 953-962 · Zbl 0953.65030
[46] V.Y. Pan, M. Abu Tabanjeh, Z. Chen, E. Landowne, A. Sadikou, New transformations of Cauchy matrices and Trummer’s problem, Comput. Math. (with Applications) 35 (12) (1998) 1-5; V.Y. Pan, M. Abu Tabanjeh, Z. Chen, E. Landowne, A. Sadikou, New transformations of Cauchy matrices and Trummer’s problem, Comput. Math. (with Applications) 35 (12) (1998) 1-5 · Zbl 0999.65024
[47] V.Y. Pan, M. Abu Tabanjeh, Z. Chen, S. Providence, A. Sadikou, Transformations of Cauchy matrices for Trummer’s problem and a Cauchy-like linear solver, in: A. Ferreria, J. Rolim, H. Simon, S.-H. Teng (Eds.), Proceedings of the Fifth Annual International Symposium on Solving Irregularly Structured Problems in Parallel (Irregular 98), Lecture Notes in Computer Science, vol. 1457, Springer, Berlin, August 1998, pp. 274-284; V.Y. Pan, M. Abu Tabanjeh, Z. Chen, S. Providence, A. Sadikou, Transformations of Cauchy matrices for Trummer’s problem and a Cauchy-like linear solver, in: A. Ferreria, J. Rolim, H. Simon, S.-H. Teng (Eds.), Proceedings of the Fifth Annual International Symposium on Solving Irregularly Structured Problems in Parallel (Irregular 98), Lecture Notes in Computer Science, vol. 1457, Springer, Berlin, August 1998, pp. 274-284
[48] V.Y. Pan, A. Zheng, M. Abu Tabanjeh, Z. Chen, S. Providence, Superfast computations with singular structured matrices over abstract fields, in: V.G. Ganzha, E.W. Mayr, E.V. Vorontsov (Eds.), Proceedings of the Second Workshop on Computer Algebra in Scientific Computing (CASC-99), Springer, Berlin, May 1999, pp. 323-338; V.Y. Pan, A. Zheng, M. Abu Tabanjeh, Z. Chen, S. Providence, Superfast computations with singular structured matrices over abstract fields, in: V.G. Ganzha, E.W. Mayr, E.V. Vorontsov (Eds.), Proceedings of the Second Workshop on Computer Algebra in Scientific Computing (CASC-99), Springer, Berlin, May 1999, pp. 323-338 · Zbl 1086.65511
[49] Reichel, L., A matrix problem with application to rapid solution of integral equations, SIAM J. Sci. Statist. Comput., 11, 263-280 (1990) · Zbl 0725.65133
[50] Rokhlin, F., Rapid solution of integral equations of classical potential theory, J. Comput. Phys., 60, 187-207 (1985) · Zbl 0629.65122
[51] Schwartz, J. T., Fast probabilistic algorithms for verification of polynomial identities, J. ACM, 27, 4, 701-717 (1980) · Zbl 0452.68050
[52] Strassen, V., Gaussian elimination is not optimal, Numer. Math., 13, 354-356 (1969) · Zbl 0185.40101
[53] Trummer, M., An efficient implementation of a conformal mapping method using the Szegö kernel, SIAM J. Numer. Anal., 23, 853-872 (1986) · Zbl 0596.30013
[54] R.Z. Zippel, Probabilistic Algorithm for Sparse Polynominals, Proc. EUROSAM 79, Lecture Notes in Computer Science, vol. 72, Springer, Berlin, 1979, pp. 216-226; R.Z. Zippel, Probabilistic Algorithm for Sparse Polynominals, Proc. EUROSAM 79, Lecture Notes in Computer Science, vol. 72, Springer, Berlin, 1979, pp. 216-226
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.