| We extend to any input, the Greengard and Rokhlin multipole algorithm for solution to Trummer's problem or the problem of multiplying a Cauchy matrix by a vector. We use matrix transformation equations (cf. [PACLS,a]) to transform Trummer's problem into one or more special Trummer's problems, where we choose one of the input vectors. Our choice of input vector bypasses the weakness in the multipole algorithm of having some difficult inputs and along with transformation via matrix equations, allows us to exploit the speed of the FFT and inverse the FFT. We present a superfast divide-and-conquer algorithm to invert strongly nonsingular, nonsingular, and singular structured matrices of the basic classes. Operators of displacement and scaling which produce generator matrices, together with discrete cosine or discrete sine transforms (cf. [GKO95]), transform structured matrices into Cauchy-like matrices. When applicable, symmetrization is used to ensure strong nonsingularity. Randomization may transform a given input structured matrix into one of generic rank profile (GRP). A strongly nonsingular Cauchy-like matrix or a Cauchy-like matrix with GRP may be inputs to our superfast divide-and-conquer algorithm. We use short matrix generator blocks as input to our algorithm. |
