Fast approximate computations with Cauchy matrices and polynomials

Pan, Victor

doi:10.1090/mcom/3204

Fast approximate computations with Cauchy matrices and polynomials
HTML articles powered by AMS MathViewer

by Victor Y. Pan PDF

Math. Comp. 86 (2017), 2799-2826 Request permission

Abstract:

Multipoint polynomial evaluation and interpolation are fundamental for modern symbolic and numerical computing. The known algorithms solve both problems over any field of constants in nearly linear arithmetic time, but the cost grows to quadratic for numerical solution. We fix this discrepancy: our new numerical algorithms run in nearly linear arithmetic time. At first we restate our goals as the multiplication of an $n\times n$ Vandermonde matrix by a vector and the solution of a Vandermonde linear system of $n$ equations. Then we transform the matrix into a Cauchy structured matrix with some special features. By exploiting them, we approximate the matrix by a generalized hierarchically semiseparable matrix, which is a structured matrix of a different class. Finally we accelerate our solution to the original problems by applying the Fast Multipole Method to the latter matrix. Our resulting numerical algorithms run in nearly optimal arithmetic time when they perform the above fundamental computations with polynomials, Vandermonde matrices, transposed Vandermonde matrices, and a large class of Cauchy and Cauchy-like matrices. Some of our techniques may be of independent interest.

References

Steffen Börm, Construction of data-sparse $\scr H^2$-matrices by hierarchical compression, SIAM J. Sci. Comput. 31 (2009), no. 3, 1820–1839. MR 2491547, DOI 10.1137/080720693
Steffen Börm, Efficient numerical methods for non-local operators, EMS Tracts in Mathematics, vol. 14, European Mathematical Society (EMS), Zürich, 2010. $\scr H^2$-matrix compression, algorithms and analysis. MR 2767920, DOI 10.4171/091
T. Bella, Y. Eidelman, I. Gohberg, and V. Olshevsky, Computations with quasiseparable polynomials and matrices, Theoret. Comput. Sci. 409 (2008), no. 2, 158–179. MR 2474333, DOI 10.1016/j.tcs.2008.09.008
Dario Andrea Bini and Giuseppe Fiorentino, Design, analysis, and implementation of a multiprecision polynomial rootfinder, Numer. Algorithms 23 (2000), no. 2-3, 127–173. MR 1772050, DOI 10.1023/A:1019199917103
S. Börm, L. Grasedyck, and W. Hackbusch, Introduction to hierarchical matrices with applications, Engineering Analysis with Boundary Elements 27 (2003), no. 5, 405–422.
W. Hackbusch and S. Börm, Data-sparse approximation by adaptive $\scr H^2$-matrices, Computing 69 (2002), no. 1, 1–35. MR 1954142, DOI 10.1007/s00607-002-1450-4
Allan Borodin and Ian Munro, The computational complexity of algebraic and numeric problems, Elsevier Computer Science Library: Theory of Computation Series, No. 1, American Elsevier Publishing Co., Inc., New York-London-Amsterdam, 1975. MR 0468309
S. Chandrasekaran, P. Dewilde, M. Gu, W. Lyons, and T. Pals, A fast solver for HSS representations via sparse matrices, SIAM J. Matrix Anal. Appl. 29 (2006/07), no. 1, 67–81. MR 2288014, DOI 10.1137/050639028
S. Chandrasekaran, M. Gu, X. Sun, J. Xia, and J. Zhu, A superfast algorithm for Toeplitz systems of linear equations, SIAM J. Matrix Anal. Appl. 29 (2007), no. 4, 1247–1266. MR 2369294, DOI 10.1137/040617200
A. Dutt, M. Gu, and V. Rokhlin, Fast algorithms for polynomial interpolation, integration, and differentiation, SIAM J. Numer. Anal. 33 (1996), no. 5, 1689–1711. MR 1411845, DOI 10.1137/0733082
Patrick Dewilde and Alle-Jan van der Veen, Time-varying systems and computations, Kluwer Academic Publishers, Boston, MA, 1998. MR 1641480, DOI 10.1007/978-1-4757-2817-0
Y. Eidelman and I. Gohberg, A modification of the Dewilde-van der Veen method for inversion of finite structured matrices, Linear Algebra Appl. 343/344 (2002), 419–450. Special issue on structured and infinite systems of linear equations. MR 1878953, DOI 10.1016/S0024-3795(01)00363-9
Yuli Eidelman, Israel Gohberg, and Iulian Haimovici, Separable type representations of matrices and fast algorithms. Vol. 1, Operator Theory: Advances and Applications, vol. 234, Birkhäuser/Springer, Basel, 2014. Basics. Completion problems. Multiplication and inversion algorithms. MR 3137083
A. Gerasoulis, A fast algorithm for the multiplication of generalized Hilbert matrices with vectors, Math. Comp. 50 (1988), no. 181, 179–188. MR 917825, DOI 10.1090/S0025-5718-1988-0917825-9
A. Gerasoulis, M. D. Grigoriadis, and Liping Sun, A fast algorithm for Trummer’s problem, SIAM J. Sci. Statist. Comput. 8 (1987), no. 1, S135–S138. MR 873954, DOI 10.1137/0908017
Lars Grasedyck and Wolfgang Hackbusch, Construction and arithmetics of $\scr H$-matrices, Computing 70 (2003), no. 4, 295–334. MR 2011419, DOI 10.1007/s00607-003-0019-1
I. Gohberg, T. Kailath, and V. Olshevsky, Fast Gaussian elimination with partial pivoting for matrices with displacement structure, Math. Comp. 64 (1995), no. 212, 1557–1576. MR 1312096, DOI 10.1090/S0025-5718-1995-1312096-X
Gene H. Golub and Charles F. Van Loan, Matrix computations, 4th ed., Johns Hopkins Studies in the Mathematical Sciences, Johns Hopkins University Press, Baltimore, MD, 2013. MR 3024913
S. A. Goreinov, I. V. Oseledets, D. V. Savostyanov, E. E. Tyrtyshnikov, and N. L. Zamarashkin, How to find a good submatrix, Report 08-10, ICM HKBU, Kowloon Tong, Hong Kong, 2008.
S. A. Goreinov and E. E. Tyrtyshnikov, The maximal-volume concept in approximation by low-rank matrices, Structured matrices in mathematics, computer science, and engineering, I (Boulder, CO, 1999) Contemp. Math., vol. 280, Amer. Math. Soc., Providence, RI, 2001, pp. 47–51. MR 1850400, DOI 10.1090/conm/280/4620
Ellis Horowitz, A fast method for interpolation using preconditioning, Information Processing Lett. 1 (1971/72), 157–163. MR 315864, DOI 10.1016/0020-0190(72)90050-6
W. Hackbusch, A sparse matrix arithmetic based on $\scr H$-matrices. I. Introduction to $\scr H$-matrices, Computing 62 (1999), no. 2, 89–108. MR 1694265, DOI 10.1007/s006070050015
N. Halko, P. G. Martinsson, and J. A. Tropp, Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions, SIAM Rev. 53 (2011), no. 2, 217–288. MR 2806637, DOI 10.1137/090771806
Donald E. Knuth, The art of computer programming. Vol. 1: Fundamental algorithms, Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont., 1969. Second printing. MR 0286317
Edo Liberty, Franco Woolfe, Per-Gunnar Martinsson, Vladimir Rokhlin, and Mark Tygert, Randomized algorithms for the low-rank approximation of matrices, Proc. Natl. Acad. Sci. USA 104 (2007), no. 51, 20167–20172. MR 2366406, DOI 10.1073/pnas.0709640104
M. W. Mahoney, Randomized algorithms for matrices and data, Foundations and Trends in Machine Learning, NOW Publishers, 3, 2, 2011. (Abridged version in: Advances in Machine Learning and Data Mining for Astronomy, edited by M. J. Way, et al., pp. 647-672, 2012.)
P. G. Martinsson, A fast randomized algorithm for computing a hierarchically semiseparable representation of a matrix, SIAM J. Matrix Anal. Appl. 32 (2011), no. 4, 1251–1274. MR 2854612, DOI 10.1137/100786617
R. Moenck, A. Borodin, Fast Modular Transform via Division, Proc. 13th Annual Symposium on Switching and Automata Theory, 90–96, IEEE Comp. Society Press, Washington, DC, 1972.
P. G. Martinsson, V. Rokhlin, and M. Tygert, A fast algorithm for the inversion of general Toeplitz matrices, Comput. Math. Appl. 50 (2005), no. 5-6, 741–752. MR 2165636, DOI 10.1016/j.camwa.2005.03.011
Victor Pan, On computations with dense structured matrices, Math. Comp. 55 (1990), no. 191, 179–190. MR 1023051, DOI 10.1090/S0025-5718-1990-1023051-7
Victor Y. Pan, An algebraic approach to approximate evaluation of a polynomial on a set of real points, Adv. Comput. Math. 3 (1995), no. 1-2, 41–58. MR 1314901, DOI 10.1007/BF02431995
Victor Y. Pan, Structured matrices and polynomials, Birkhäuser Boston, Inc., Boston, MA; Springer-Verlag, New York, 2001. Unified superfast algorithms. MR 1843842, DOI 10.1007/978-1-4612-0129-8
Victor Y. Pan, Transformations of matrix structures work again, Linear Algebra Appl. 465 (2015), 107–138. MR 3274665, DOI 10.1016/j.laa.2014.09.004
Victor Y. Pan, How bad are Vandermonde matrices?, SIAM J. Matrix Anal. Appl. 37 (2016), no. 2, 676–694. MR 3504989, DOI 10.1137/15M1030170
V. Y. Pan, Fast approximation algorithms for computations with Cauchy matrices, polynomials, and rational functions, arXiv:1506.02285 [math.NA] 34 pages, 7 figures, 8 tables, June 7, 2015, revised in April 2016.
Victor Y. Pan, Qi Luan, John Svadlenka, and Liang Zhao, Primitive and cynical low rank approximation, preprocessing and extensions, arXiv:1611.01391 [math.NA] (47 pages, 7 figures, 5 tables), April 2017.
Victor Y. Pan, Guoliang Qian, and Xiaodong Yan, Random multipliers numerically stabilize Gaussian and block Gaussian elimination: proofs and an extension to low-rank approximation, Linear Algebra Appl. 481 (2015), 202–234. MR 3349652, DOI 10.1016/j.laa.2015.04.021
V. Pan, J. H. Reif, and S. R. Tate, The Power of Combining the Techniques of Algebraic and Numerical Computing, Procs. of FOCS’92, IEEE Comp. Soc. Press, 1992, pp. 703–713.
Victor Pan, Akimou Sadikou, Elliott Landowne, and Olen Tiga, A new approach to fast polynomial interpolation and multipoint evaluation, Comput. Math. Appl. 25 (1993), no. 9, 25–30. MR 1208387, DOI 10.1016/0898-1221(93)90129-J
Victor Y. Pan, Ailong Zheng, Xiaohan Huang, and Yanqiang Yu, Fast multipoint polynomial evaluation and interpolation via computations with structured matrices, Ann. Numer. Math. 4 (1997), no. 1-4, 483–510. The heritage of P. L. Chebyshev: a Festschrift in honor of the 70th birthday of T. J. Rivlin. MR 1422699
V. Rokhlin, Rapid solution of integral equations of classical potential theory, J. Comput. Phys. 60 (1985), no. 2, 187–207. MR 805870, DOI 10.1016/0021-9991(85)90002-6
E. E. Tyrtyshnikov, Incomplete cross approximation in the mosaic-skeleton method, Computing 64 (2000), no. 4, 367–380. International GAMM-Workshop on Multigrid Methods (Bonn, 1998). MR 1783468, DOI 10.1007/s006070070031
R. Vandebril, M. Van Barel, N. Mastronardi, Matrix Computations and Semiseparable Matrices (Volumes 1 and 2), The Johns Hopkins University Press, Baltimore, Maryland, 2007/2008.
David P. Woodruff, Sketching as a tool for numerical linear algebra, Found. Trends Theor. Comput. Sci. 10 (2014), no. 1-2, iv+157. MR 3285427, DOI 10.1561/0400000060
Jianlin Xia, On the complexity of some hierarchical structured matrix algorithms, SIAM J. Matrix Anal. Appl. 33 (2012), no. 2, 388–410. MR 2970212, DOI 10.1137/110827788
Yuanzhe Xi, Jianlin Xia, Stephen Cauley, and Venkataramanan Balakrishnan, Superfast and stable structured solvers for Toeplitz least squares via randomized sampling, SIAM J. Matrix Anal. Appl. 35 (2014), no. 1, 44–72. MR 3152737, DOI 10.1137/120895755
Jianlin Xia, Yuanzhe Xi, and Ming Gu, A superfast structured solver for Toeplitz linear systems via randomized sampling, SIAM J. Matrix Anal. Appl. 33 (2012), no. 3, 837–858. MR 3023454, DOI 10.1137/110831982