Abstract
The papers [18], [9], [29], and [28] combine the techniques of the Fast Multipole Method of [15], [8] with the transformations of matrix structures, traced back to [19]. The resulting numerically stable algorithms approximate the solutions of Toeplitz, Hankel, Toeplitz-like, and Hankel-like linear systems of equations in nearly linear arithmetic time, versus the classical cubic time and the quadratic time of the previous advanced algorithms. We extend this progress to decrease the arithmetic time of the known numerical algorithms from quadratic to nearly linear for computations with matrices that have structure of Cauchy or Vandermonde type and for the evaluation and interpolation of polynomials and rational functions. We detail and analyze the new algorithms, and in [21] we extend them further.
Some preliminary results of this paper have been presented at CASC 2013. Our research has been supported by the NSF Grant CC 1116736 and the PSC CUNY Awards 64512–0042 and 65792–0043.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bracewell, R.: The Fourier Transform and Its Applications, 3rd edn. McGraw-Hill, New York (1999)
Börm, S.: Efficient Numerical Methods for Non-local Operators: \(\mathcal H^2\)-Matrix Compression, Algorithms and Analysis. European Math. Society (2010)
Bella, T., Eidelman, Y., Gohberg, I., Olshevsky, V.: Computations with Quasiseparable Polynomials and Matrices. Theoretical Computer Science 409(2), 158–179 (2008)
Bini, D.A., Fiorentino, G.: Design, Analysis, and Implementation of a Multiprecision Polynomial Rootfinder. Numer. Algs. 23, 127–173 (2000)
Bini, D., Pan, V.Y.: Polynomial and Matrix Computations, Volume 1: Fundamental Algorithms. Birkhäuser, Boston (1994)
Barba, L.A., Yokota, R.: How Will the Fast Multipole Method Fare in Exascale Era? SIAM News 46(6), 1–3 (2013)
Chandrasekaran, S., Dewilde, P., Gu, M., Lyons, W., Pals, T.: A Fast Solver for HSS Representations via Sparse Matrices. SIAM J. Matrix Anal. Appl. 29(1), 67–81 (2006)
Carrier, J., Greengard, L., Rokhlin, V.: A Fast Adaptive Algorithm for Particle Simulation. SIAM J. Scientific Computing 9, 669–686 (1998)
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, 1247–1266 (2007)
Dutt, A., Gu, M., Rokhlin, V.: Fast Algorithms for Polynomial Interpolation, Integration, and Differentiation. SIAM Journal on Numerical Analysis 33(5), 1689–1711 (1996)
Dewilde, P., van der Veen, A.: Time-Varying Systems and Computations. Kluwer Academic Publishers, Dordrecht (1998)
Eidelman, Y., Gohberg, I.: A Modification of the Dewilde–van der Veen Method for Inversion of Finite Structured Matrices. Linear Algebra and Its Applications 343, 419–450 (2002)
Eidelman, Y., Gohberg, I., Haimovici, I.: Separable Type Representations of Matrices and Fast Algorithms. Birkhäuser (2013)
Gohberg, I., Kailath, T., Olshevsky, V.: Fast Gaussian Elimination with Partial Pivoting for Matrices with Displacement Structure. Mathematics of Computation 64, 1557–1576 (1995)
Greengard, L., Rokhlin, V.: A Fast Algorithm for Particle Simulation. Journal of Computational Physics 73, 325–348 (1987)
Gentelman, W., Sande, G.: Fast Fourier Transform for Fun and Profit. Full Joint Comput. Conference 29, 563–578 (1966)
Lipton, R.J., Rose, D., Tarjan, R.E.: Generalized Nested Dissection. SIAM J. on Numerical Analysis 16(2), 346–358 (1979)
Martinsson, P.G., Rokhlin, V., Tygert, M.: A Fast Algorithm for the Inversion of Toeplitz Matrices. Comput. Math. Appl. 50, 741–752 (2005)
Pan, V.Y.: On Computations with Dense Structured Matrices, Math. of Computation, 55(191), 179–190 (1990); Also in Proc. Intern. Symposium on Symbolic and Algebraic Computation (ISSAC 1989), 34–42. ACM Press, New York (1989)
Pan, V.Y.: Structured Matrices and Polynomials: Unified Superfast Algorithms. Birkhäuser/Springer, Boston/New York (2001)
Pan, V.Y.: Transformations of Matrix Structures Work Again II, In: arxiv:1311.3729[math.NA]
Pan, V.Y.: Fast Approximation Algorithms for Computations with Cauchy Matrices and Extensions, in arxiv and Tech. Report TR 201400x, PhD Program in Comp. Sci., Graduate Center, CUNY (2014)
Pan, V.Y., Reif, J.: Fast and Efficient Parallel Solution of Sparse Linear Systems. SIAM J. on Computing 22(6), 1227–1250 (1993)
Rokhlin, V.: Rapid Solution of Integral Equations of Classical Potential Theory. Journal of Computational Physics 60, 187–207 (1985)
Vandebril, R., Van Barel, M., Mastronardi, N.: Matrix Computations and Semiseparable Matrices: Linear Systems, vol. 1. The Johns Hopkins University Press, Baltimore (2007)
Xia, J.: On the Complexity of Some Hierarchical Structured Matrix Algorithms. SIAM J. Matrix Anal. Appl. 33, 388–410 (2012)
Xia, J.: Randomized Sparse Direct Solvers. SIAM J. Matrix Anal. Appl. 34, 197–227 (2013)
Xia, J., Xi, Y., Cauley, S., Balakrishnan, V.: Superfast and Stable Structured Solvers for Toeplitz Least Squares via Randomized Sampling. SIAM J. Matrix Anal. and Applications 35, 44–72 (2014)
Xia, J., Xi, Y., Gu, M.: A Superfast Structured Solver for Toeplitz Linear Systems via Randomized Sampling. SIAM J. Matrix Anal. Appl. 33, 837–858 (2012)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Pan, V.Y. (2014). Fast Approximate Computations with Cauchy Matrices, Polynomials and Rational Functions. In: Hirsch, E.A., Kuznetsov, S.O., Pin, JÉ., Vereshchagin, N.K. (eds) Computer Science - Theory and Applications. CSR 2014. Lecture Notes in Computer Science, vol 8476. Springer, Cham. https://doi.org/10.1007/978-3-319-06686-8_22
Download citation
DOI: https://doi.org/10.1007/978-3-319-06686-8_22
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-06685-1
Online ISBN: 978-3-319-06686-8
eBook Packages: Computer ScienceComputer Science (R0)