krylov 0.0.3

Iterative methods for linear equation systems.

Forked from André Gaul's KryPy, krylov provides Krylov subspace methods for Python. It is more advanced than SciPy's linalg methods in that it

• return many interesting statistics, e.g., the residual norms,
• lets the user adjust more parameters, e.g., the orthogonalization method in GMRES,
• allows arbitrary inner products, and
• is fully blocked/vectorized.

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

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.cg(A, b)
# sol, info = krylov.minres(A, b)
sol, info = krylov.gmres(A, b)

# sol is None if no solution has been found
# info.resnorms contains the relative residual norms and some more data

# plot residuals
import matplotlib.pyplot as plt

plt.semilogy(info.resnorms)
plt.show()

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)

Discoveror 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 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 (with Saunders).

Michael Saunders

Discoverer of MINRES, SYMMLQ (with Paige).

Books

• Yousef Saad, Iterative Krylov Methods for Large Linear Systems

• Henk A. van der Vorst, Iterative Methods for Sparse Linear Systems

• Jörg Liesen and Zdeněk Strakoš, Krylov Subspace Methods

• R. Barrett et al., Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods

Advantages over SciPy

• Works with SciPy sparse matrices, NumPy arrays, custom LinearOperators
• Supports custom inner products
• Returns residual norms and other interesting data
• Full Python implementation
• Fully vectorized, can deal with multiple right-hand sides
• Supports floats and complex data

Testing

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

tox -- --maxfail=1

License

This software is published under the MIT license.