AJCM  Vol.4 No.5 , December 2014
Fast and Numerically Stable Approximate Solution of Trummer’s Problem
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.
Cite this paper: 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.

[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.