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
Published electronically: April 28, 2017
MathSciNet review: 3667025
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?)

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

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