Fast and Numerically Stable Approximate Solution of Trummer’s Problem

Abstract Full-Text HTML XML Download as PDF (Size:2567KB) PP. 387-395

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.

Conflicts of Interest

The authors declare no conflicts of interest.

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