krylov 0.1.0

Krylov subspace methods for Python

Iterative methods for linear equation systems.

krylov provides Krylov subspace methods for the solution of linear systems in Python. Install with

pip install krylov

and use as

import numpy
import krylov

A = numpy.diag([1.0e-3] + list(range(2, 101)))
b = numpy.ones(100)

sol, info = krylov.gmres(A, b)

# sol is None if no solution has been found
info.success  # Boolean
info.xk  # the last iterate; equal to sol if success
info.numsteps  # number of iterations
info.resnorms  # relative residual norms
info.nresnorms  # resnorms of the normalized equations ||A.H (b - Ax)||
info.acond  # estimate of cond(A)
info.anorm  # estimate of the Frobenius norm of A
info.xnorm  # estimate of norm(x)
info.reason  # if not successful, reason

krylov provides the following Krylov subspace methods for solving linear equation systems:

BiCG, BiCGSTAB, CG, CGNE, CGNR, CGR, CGS, Chebyshev, GCR, GMRES, MINRES, QMR, SYMMLQ, TFQMR.

For solving least-squares problems, krylov has

CGLS, LSMR, LSQR

Craig's method solves the minimization problem

\text{Minimize } \|x\| \text{s.t.} Ax=b.

Additionally, krylov provides the stationary methods

Gauss-Seidel, Jacobi, Richardson, SOR, SSOR.

All methods

• return many interesting statistics, e.g., the residual norms,
• are fully blocked/vectorized, can deal with multiple right-hand sides,
• have callback for retrieving/manipulating internal solver data,
• support real and complex data,
• work with SciPy sparse matrices, NumPy arrays, custom LinearOperators,
• allow arbitrary inner products, and
• let the user adjust various parameters, e.g., the orthogonalization method in GMRES.

krylov is written completely in Python, so methods can be easily adapted.

Other Krylov software

• pykrylov - A library of Krylov methods in pure Python.
• KryPy - Another Python package for Krylov subspace methods.
• scipy.sparse.linalg - SciPy's implementation of Krylov methods. Uses the Fortran implementations of the Templates for the Solution of Linear Systems
• PETSc - Parallel high-performance implementation of many Krylov methods in C.
• Krylov.jl - A Julia Basket of Hand-Picked Krylov Methods.

Team Krylov

Some important figures in Krylov subspace method, ordered by date of birth.

Aleksey N. Krylov (1863–1945)

Алексе́й Никола́евич Крыло́в, Russian naval engineer, applied mathematician and memoirist. Krylov wrote about 300 papers and books. They span a wide range of topics, including shipbuilding, magnetism, artillery, mathematics, astronomy, and geodesy. In 1904 he built the first machine in Russia for integrating Ordinary differential equations. In 1931 (aged 68) he published a paper on what is now called the Krylov subspace and Krylov subspace methods.

Cornelius Lanczos (1893–1974)

Extensive contributions all over numerical analysis and physics. For example, Lanczos pioneered FFT, introduced Chebyshev polynomials to numerics, and devised the Lanczos algorithm for eigenvalue computations.

Assistant to Einstein in Berlin. Later one of the "Martians", a group of Hungarian scientists who emigrated to the US in the first half the 20th century.

In 1972, aged 79, Lanczos gave two extensive interviews which are recorded on video and can be watched on YouTube:

• Lanczos about his life
• Lanczos about mathematics

Alston Scott Householder (1904–1993)

Discoverer of the Householder transformation and of Householder's method. SIAM and ACM president, organizer of the Gatlinburg conferences, now named Householder Symposia.

Magnus Hestenes (1906–1991)

Best known for his contributions to calculus of variations and optimal control, pioneer in in computer science. Co-discoverer (with Lanczos and Stiefel) of the conjugate gradient method (CG).

AMS vice president.

Eduard Stiefel (1909–1978)

Ground-breaking contributions in the fields of algebraic topology. Co-discoverer (with Lanczos and Hestenes) of CG.

Also active as a military officer, rising to the rank of colonel (Oberst der Artillerie) in the Swiss army during World War II.

J. Wallace Givens (1910–1993)

Pioneer in computer science. Director of the Division of Applied Mathematics at the Argonne National Labs. SIAM president. Givens rotations are named after him.

Walter Edwin Arnoldi (1917–1995)

American engineer, mainly known for the discovery of the Arnoldi iteration which for Hermitian matrices, reduces to the Lanczos algorithm.

Henk van der Vorst (1944–)

Various important contributions in Krylov subspace methods and related topics. Discoverer of the BiCGSTAB method and the Jacobi-Davidson method.

Since 2006, van der Vorst works as an artist.

YouTube: Galerie Laimböck -- Henk van der Vorst ‘Geometrische Origami’ (Dutch)

Yousef Saad (1950–)

Various important contributions in Krylov subspace methods and related topics. Discoverer of GCR and GMRES (with Martin H. Schultz).

YouTube: Filtering techniques for eigenvalue problems, Saad

Christopher Paige

Discoverer of MINRES, SYMMLQ, and LSQR (with Saunders).

Michael Saunders

Discoverer of MINRES, SYMMLQ, LSQR (with Paige), and LSMR (with Fong).

Books

• R. Barrett et al., Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods, 1994
• C.T. Kelley, Iterative Methods for Linear and Nonlinear Equations, 1995
• Anne Greenbaum, Iterative Methods for Solving Linear Systems, 1997
• James W. Demmel, Applied Numerical Linear Algebra, 1997
• Yousef Saad, Iterative Methods for Sparse Linear Systems, 2003
• Henk A. van der Vorst, Iterative Krylov Methods for Large Linear Systems, 2003
• Jörg Liesen and Zdeněk Strakoš, Krylov Subspace Methods - Principles and Analysis, 2012

Testing

To run the krylov unit tests, check out this repository and type, e.g.,

tox -- --maxfail=1