Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

Fast approximate computations with Cauchy matrices and polynomials


Author: Victor Y. Pan
Journal: Math. Comp. 86 (2017), 2799-2826
MSC (2010): Primary 12Y05, 15A04, 47A65, 65D05, 68Q25
DOI: https://doi.org/10.1090/mcom/3204
Published electronically: April 28, 2017
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [B09] Steffen Börm, Construction of data-sparse $ \mathcal {H}^2$-matrices by hierarchical compression, SIAM J. Sci. Comput. 31 (2009), no. 3, 1820-1839. MR 2491547, https://doi.org/10.1137/080720693
  • [B10] Steffen Börm, Efficient Numerical Methods for Non-Local Operators: $ \mathcal {H}^2$-Matrix Compression, Algorithms and Analysis, EMS Tracts in Mathematics, vol. 14, European Mathematical Society (EMS), Zürich, 2010. MR 2767920
  • [BEGO08] 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, https://doi.org/10.1016/j.tcs.2008.09.008
  • [BF00] 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, https://doi.org/10.1023/A:1019199917103
  • [BGH03] 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.
  • [BH02] W. Hackbusch and S. Börm, Data-sparse approximation by adaptive $ \mathcal {H}^2$-matrices, Computing 69 (2002), no. 1, 1-35. MR 1954142, https://doi.org/10.1007/s00607-002-1450-4
  • [BM75] Allan Borodin and Ian Munro, The Computational Complexity of Algebraic and Numeric Problems, American Elsevier Publishing Co., Inc., New York-London-Amsterdam, 1975. Elsevier Computer Science Library; Theory of Computation Series, No. 1. MR 0468309
  • [CDG06] 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, https://doi.org/10.1137/050639028
  • [CGS07] 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, https://doi.org/10.1137/040617200
  • [DGR96] 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, https://doi.org/10.1137/0733082
  • [DV98] Patrick Dewilde and Alle-Jan van der Veen, Time-Varying Systems and Computations, Kluwer Academic Publishers, Boston, MA, 1998. MR 1641480
  • [EG02] 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, https://doi.org/10.1016/S0024-3795(01)00363-9
  • [EGH13] Yuli Eidelman, Israel Gohberg, and Iulian Haimovici, Separable Type Representations of Matrices and Fast Algorithms. Vol. 1: Basics. Completion Problems. Multiplication and Inversion Algorithms, Operator Theory: Advances and Applications, vol. 234, Birkhäuser/Springer, Basel, 2014. MR 3137083
  • [G88] A. Gerasoulis, A fast algorithm for the multiplication of generalized Hilbert matrices with vectors, Math. Comp. 50 (1988), no. 181, 179-188. MR 917825, https://doi.org/10.2307/2007921
  • [GGS87] 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, https://doi.org/10.1137/0908017
  • [GH03] Lars Grasedyck and Wolfgang Hackbusch, Construction and arithmetics of $ \mathcal {H}$-matrices, Computing 70 (2003), no. 4, 295-334. MR 2011419, https://doi.org/10.1007/s00607-003-0019-1
  • [GKO95] 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, https://doi.org/10.2307/2153371
  • [GL13] 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
  • [GOS08] 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.
  • [GT01] 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, https://doi.org/10.1090/conm/280/4620
  • [H72] Ellis Horowitz, A fast method for interpolation using preconditioning, Information Processing Lett. 1 (1971/72), 157-163. MR 0315864
  • [H99] W. Hackbusch, A sparse matrix arithmetic based on $ \mathcal {H}$-matrices. I. Introduction to $ \mathcal {H}$-matrices, Computing 62 (1999), no. 2, 89-108. MR 1694265, https://doi.org/10.1007/s006070050015
  • [HMT11] 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, https://doi.org/10.1137/090771806
  • [K68] Donald E. Knuth, The Art of Computer Programming. Vol. 1: Fundamental Algorithms, Addison-Wesley, Reading, MA, 1997. Third edition [of MR 0286317]. MR 3077152
  • [LWMRT] 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, https://doi.org/10.1073/pnas.0709640104
  • [M11] 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.)
  • [M11a] 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, https://doi.org/10.1137/100786617
  • [MB72] 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.
  • [MRT05] 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, https://doi.org/10.1016/j.camwa.2005.03.011
  • [P90] Victor Pan, On computations with dense structured matrices, Math. Comp. 55 (1990), no. 191, 179-190. MR 1023051, https://doi.org/10.2307/2008798
  • [P95] 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, https://doi.org/10.1007/BF02431995
  • [P01] Victor Y. Pan, Structured Matrices and Polynomials: Unified Superfast Algorithms, Birkhäuser Boston, Inc., Boston, MA; Springer-Verlag, New York, 2001. MR 1843842
  • [P15] Victor Y. Pan, Transformations of matrix structures work again, Linear Algebra Appl. 465 (2015), 107-138. MR 3274665, https://doi.org/10.1016/j.laa.2014.09.004
  • [Pa16] Victor Y. Pan, How bad are Vandermonde matrices?, SIAM J. Matrix Anal. Appl. 37 (2016), no. 2, 676-694. MR 3504989, https://doi.org/10.1137/15M1030170
  • [Pb] 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.
  • [PLSZa] 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.
  • [PQY15] 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, https://doi.org/10.1016/j.laa.2015.04.021
  • [PRT92] 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.
  • [PSLT93] 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, https://doi.org/10.1016/0898-1221(93)90129-J
  • [PZHY97] 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. MR 1422699
  • [R85] V. Rokhlin, Rapid solution of integral equations of classical potential theory, J. Comput. Phys. 60 (1985), no. 2, 187-207. MR 805870, https://doi.org/10.1016/0021-9991(85)90002-6
  • [T00] E. E. Tyrtyshnikov, Incomplete cross approximation in the mosaic-skeleton method, Computing 64 (2000), no. 4, 367-380. MR 1783468, https://doi.org/10.1007/s006070070031
  • [VVM] 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.
  • [W14] 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
  • [X12] Jianlin Xia, On the complexity of some hierarchical structured matrix algorithms, SIAM J. Matrix Anal. Appl. 33 (2012), no. 2, 388-410. MR 2970212, https://doi.org/10.1137/110827788
  • [XXCB14] 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, https://doi.org/10.1137/120895755
  • [XXG12] 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, https://doi.org/10.1137/110831982

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 12Y05, 15A04, 47A65, 65D05, 68Q25

Retrieve articles in all journals with MSC (2010): 12Y05, 15A04, 47A65, 65D05, 68Q25


Additional Information

Victor Y. Pan
Affiliation: Departments of Mathematics and Computer Science, Lehman College and the Graduate Center of the City University of New York, Bronx, New York 10468
Email: victor.pan@lehman.cuny.edu

DOI: https://doi.org/10.1090/mcom/3204
Keywords: Polynomial evaluation, rational evaluation, interpolation, Vandermonde matrices, transformation of matrix structures, Cauchy matrices, fast multipole method, HSS matrices, matrix compression
Received by editor(s): June 7, 2015
Received by editor(s) in revised form: April 20, 2016, and July 6, 2016
Published electronically: April 28, 2017
Additional Notes: Some results of this paper have been presented at ILAS’2013, Providence, RI, 2013, at CASC’2013, Berlin, Germany, 2013, and at CSR’2014, Moscow, Russia, 2014
Article copyright: © Copyright 2017 American Mathematical Society

American Mathematical Society