Cauchy Matrix - Generalization

Generalization

A matrix C is called Cauchy-like if it is of the form

Defining X=diag(x_i), Y=diag(y_i), one sees that both Cauchy and Cauchy-like matrices satisfy the displacement equation

(with for the Cauchy one). Hence Cauchy-like matrices have a common displacement structure, which can be exploited while working with the matrix. For example, there are known algorithms in literature for

• approximate Cauchy matrix-vector multiplication with ops (e.g. the fast multipole method),
• (pivoted) LU factorization with ops (GKO algorithm), and thus linear system solving,
• approximated or unstable algorithms for linear system solving in .

Here denotes the size of the matrix (one usually deals with square matrices, though all algorithms can be easily generalized to rectangular matrices).