Fast and Numerically Stable Approximate Solution of Trummer’s Problem

DOI: 10.4236/ajcm.2014.45033   PDF   HTML   XML   2,572 Downloads   3,259 Views  

Abstract

Trummer’s problem is the problem of multiplication of an n × n Cauchy matrix C by a vector. It serves as the basis for the solution of several problems in scientific computing and engineering [1]. The straightforward algorithm solves Trummer’s problem in O(n2) flops. The fast algorithm solves the problem in O(nlog2n) flops [2] but has poor numerical stability. The algorithm we discuss here in this paper is the celebrated multipoint algorithm [3] which has been studied by Pan et al. The algorithm approximates the solution in O(nlogn) flops in terms of n but its cost estimate depends on the bound of the approximation error and also depends on the correlation between the entries of the pair of n-dimensional vectors defining the input matrix C.

Share and Cite:

Tabanjeh, M. (2014) Fast and Numerically Stable Approximate Solution of Trummer’s Problem. American Journal of Computational Mathematics, 4, 387-395. doi: 10.4236/ajcm.2014.45033.

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1] Rokhlin, V. (1985) Rapid Solution of Integral Equations of Classical Potential Theory. Journal of Computational Physics, 60, 187-207. http://dx.doi.org/10.1016/0021-9991(85)90002-6
[2] Gerasoulis, A. (1987) A Fast Algorithm for the Multiplication of Generalized Hilbert Matrices with Vectors. Mathematics of Computation, 50, 179-188. http://dx.doi.org/10.1090/S0025-5718-1988-0917825-9
[3] Greengard, L. and Rokhlin, V. (1987) A Fast Algorithm for Practice Simulation. Journal of Computational Physics, 73, 325-348. http://dx.doi.org/10.1016/0021-9991(87)90140-9
[4] Pan, V.Y., Zheng, A., Huany, X. and Yu, Y. (1995) Fast Multipoint Polynomial Evaluation and Interpolation via Computation with Structured Matrices. Annals of Numerical Mathematics, 4, 483-510.
[5] Pan, V.Y. (2001) Structured Matrices and Polynomials, Unified Superfast Algorithms. Birkhauser, Boston.
http://dx.doi.org/10.1007/978-1-4612-0129-8
[6] Bini, D. and Pan, V.Y. (1994) Polynomial and Matrix Computations, Volume 1: Fundamental Algorithms. Birkhauser, Boston. http://dx.doi.org/10.1007/978-1-4612-0265-3
[7] Pan, V.Y., Tabanjeh, M., Chen, Z., Landowne, E. and Sadikou, A. (1998) New Transformations of Cauchy Matrices and Trummer’s Problem. Computers & Mathematics with Applications, 35, 1-5.
http://dx.doi.org/10.1016/S0898-1221(98)00091-1
[8] Fink, T., Heinig, G. and Rost, K. (1993) An Inversion Formula and Fast Algorithms for Cauchy-Vandermonde Matrices. Linear Algebra & Its Applications, 183, 179-191. http://dx.doi.org/10.1016/0024-3795(93)90431-M
[9] Pan, V.Y., Landowne, E., Sadikou, A. and Tiga, O. (1993) A New Approach to Fast Polynomial Interpolation and Multipoint Evaluation. Computers & Mathematics with Applications, 25, 25-30.
http://dx.doi.org/10.1016/0898-1221(93)90129-J
[10] Pan, V.Y. (1995) An Algebraic Approach to Approximate Evaluation of a Polynomial on a Set of Real Points. Advances in Computational Mathematics, 3, 41-58. http://dx.doi.org/10.1007/BF02431995

  
comments powered by Disqus

Copyright © 2020 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.