TITLE:
Fast and Numerically Stable Approximate Solution of Trummer’s Problem
AUTHORS:
Mohammad M. Tabanjeh
KEYWORDS:
Cauchy Matrix, Mulipoint Algorithm, Structure Matrices, Displacement Operators
JOURNAL NAME:
American Journal of Computational Mathematics,
Vol.4 No.5,
November
11,
2014
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.