2017

On the singular values of matrices with high displacement rank

Townsend, Alex, Wilber, Heather

Understand

We introduce a new ADI-based low rank solver for $AX-XB=F$, where $F$ has rapidly decaying singular values.

Our approach results in both theoretical and practical gains, including (1) the derivation of new bounds on singular values for classes of matrices with high displacement rank, (2) a practical algorithm for solving certain Lyapunov and Sylvester matrix equations with high rank right-hand sides, and (3) a collection of low rank Poisson solvers that achieve spectral accuracy and optimal computational complexity.

Built on

The numerical solution of parabolic and elliptic differential equations,
D. W. Peaceman, H. H. Rachford, · 1955
Earlier work this paper cites.
Optimum alternating-direction-implicit iteration parameters for a model problem,
E. L. Wachspress, · 1962
Earlier work this paper cites.
Matrix equation XA+BX=C,
R. Smith, · 1968
Earlier work this paper cites.
Zolotarev problems connected with rational functions,
A. A. Gonchar, · 1969
Earlier work this paper cites.
Rational functions, capacities and approximation,
T. Ganelius, · 1979
Earlier work this paper cites.
A fast algorithm for particle simulations,
L. Greengard, V. Rokhlin, · 1987
Earlier work this paper cites.
N. I. Akhiezer, Elements of the theory of elliptic functions, volume 79, Amer. Math. Soc., 1990
1990
Earlier work this paper cites.
Solution of Lyapunov equations by alternating direction implicit iteration,
A. Lu, E. L. Wachspress, · 1991
Earlier work this paper cites.
Near-circularity for the rational Zolotarev problem in the complex plane,
G. Starke, · 1992
Earlier work this paper cites.
Two applications of a bound on the Hadamard product with a Cauchy matrix,
R. A. Horn, F. Kittaneh, · 1998
Earlier work this paper cites.
Eigenvalue decay bounds for solutions of Lyapunov equations: the symmetric case,
T. Penzl, · 2000
Earlier work this paper cites.
On the decay rate of Hankel singular values and related issues,
A. C. Antoulas, D. C. Sorensen, Y. Zhou, · 2002
Earlier work this paper cites.

Similar

A modified low-rank Smith method for large-scale Lyapunov equations,
S. Gugercin, D. C. Sorensen, A. C. Antoulas, · 2003
Cited alongside, same era.
Existence and computation of low Kronecker-rank approximations for large linear systems of tensor product structure,
L. Grasedyck, · 2004
Cited alongside, same era.
A. C. Antoulas, Approximation of large-scale dynamical systems, SIAM, 2005
2005
Cited alongside, same era.
P. Benner, V. Mehrmann, D. C. Sorensen, Dimension reduction of large-scale systems, volume 45, Springer, 2005
2005
Cited alongside, same era.
J. Sabino, Solution of large-scale Lyapunov equations via the block modified Smith method, Ph.D. thesis, Rice University, 2007
2007
Cited alongside, same era.
M. Bebendorf, Hierarchical matrices, volume 63 of Lecture Notes in Computational Science and Engineering, Springer-Verlag, Berlin, 2008
2008
Cited alongside, same era.
Exact matrix completion via convex optimization,
E. J. Candès, B. Recht, · 2009
Cited alongside, same era.
On the ADI method for Sylvester equations,
P. Benner, R.-C. Li, N. Truhar, · 2009
Cited alongside, same era.
On the efficient computation of high-dimensional integrals and the approximation by exponential sums,
D. Braess, W. Hackbusch, · 2009
Cited alongside, same era.
F. W. Olver, D. W. Lozier, R. F. Boisvert, NIST handbook of mathematical functions, Cambridge University Press, 2010
2010
Cited alongside, same era.
An error analysis for rational Galerkin projection applied to the Sylvester equation,
B. Beckermann, · 2011
Cited alongside, same era.
G. H. Golub, C. F. Van Loan, Matrix computations, volume 3, JHU Press, 2012
2012
Cited alongside, same era.

Then

C. Badea, B. Beckermann, Spectral Sets, Chapman and Hall/CRC, Chapter 37 of L. Hogben, Handbook of Linear Algebra, second edition, 2013
2013
Later among the works it cites.
A fast and well-conditioned spectral method,
S. Olver, A. Townsend, · 2013
Later among the works it cites.
S. D. Shank, Low-rank Solution Methods for Large-scale Linear Matrix Equations, Ph.D. thesis, Temple University, 2014
2014
Later among the works it cites.
A. Townsend, Computing with functions in two dimensions, Ph.D. thesis, University of Oxford, 2014
2014
Later among the works it cites.
T. A. Driscoll, N. Hale, L. N. Trefethen (Eds.), Chebfun Guide, Pafnuty Publications, Oxford, 2014
2014
Later among the works it cites.
On low-rank approximability of solutions to high-dimensional operator equations and eigenvalue problems,
D. Kressner, A. Uschmajew, · 2016
Later among the works it cites.
Computational methods for linear matrix equations,
V. Simoncini, · 2016
Later among the works it cites.
Computing with functions in spherical and polar geometries I. the sphere,
A. Townsend, H. Wilber, G. B. Wright, · 2016
Later among the works it cites.
On the singular values of matrices with displacement structure,
B. Beckermann, A. Townsend, · 2017
Closest in time.
Fast Poisson solvers for spectral methods,
Original
D. Fortunato, A. Townsend, · 2017
Closest in time.
Computing with functions in spherical and polar geometries II. the disk,
H. Wilber, A. Townsend, G. B. Wright, · 2017
Closest in time.
D. Kressner, 2017. Personal communication
2017
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…