Fast and Numerically Stable Approximate Solution of Trummer’s Problem


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.


[1] Rokhlin, V. (1985) Rapid Solution of Integral Equations of Classical Potential Theory. Journal of Computational Physics, 60, 187-207.
[2] Gerasoulis, A. (1987) A Fast Algorithm for the Multiplication of Generalized Hilbert Matrices with Vectors. Mathematics of Computation, 50, 179-188.
[3] Greengard, L. and Rokhlin, V. (1987) A Fast Algorithm for Practice Simulation. Journal of Computational Physics, 73, 325-348.
[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.
[6] Bini, D. and Pan, V.Y. (1994) Polynomial and Matrix Computations, Volume 1: Fundamental Algorithms. Birkhauser, Boston.
[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.
[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.
[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.
[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.

Copyright © 2022 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.