A fast solver for linear systems with displacement structure

Details A fast solver for linear systems with displacement structure A fast solver for linear systems with displacement structure

2010-04-12

arxiv.org/abs/1004.1988v1

Mathematics

Numerical Analysis

27 pages, 6 figures

Scientific paper

We describe a fast solver for linear systems with reconstructable Cauchy-like structure, which requires O(rn^2) floating point operations and O(rn) memory locations, where n is the size of the matrix and r its displacement rank. The solver is based on the application of the generalized Schur algorithm to a suitable augmented matrix, under some assumptions on the knots of the Cauchy-like matrix. It includes various pivoting strategies, already discussed in the literature, and a new algorithm, which only requires reconstructability. We have developed a software package, written in Matlab and C-MEX, which provides a robust implementation of the above method. Our package also includes solvers for Toeplitz(+Hankel)-like and Vandermonde-like linear systems, as these structures can be reduced to Cauchy-like by fast and stable transforms. Numerical experiments demonstrate the effectiveness of the software.

Affiliated with

Also associated with

No associations

Rating

A fast solver for linear systems with displacement structure does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A fast solver for linear systems with displacement structure, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A fast solver for linear systems with displacement structure will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-263071