In
computer science
Computer science is the study of computation, information, and automation. Computer science spans Theoretical computer science, theoretical disciplines (such as algorithms, theory of computation, and information theory) to Applied science, ...
, the block Lanczos algorithm is an
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of Rigour#Mathematics, mathematically rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algo ...
for finding the
nullspace of a
matrix
Matrix (: matrices or matrixes) or MATRIX may refer to:
Science and mathematics
* Matrix (mathematics), a rectangular array of numbers, symbols or expressions
* Matrix (logic), part of a formula in prenex normal form
* Matrix (biology), the m ...
over a
finite field
In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field (mathematics), field that contains a finite number of Element (mathematics), elements. As with any field, a finite field is a Set (mathematics), s ...
, using only multiplication of the matrix by long, thin matrices. Such matrices are considered as vectors of
tuple
In mathematics, a tuple is a finite sequence or ''ordered list'' of numbers or, more generally, mathematical objects, which are called the ''elements'' of the tuple. An -tuple is a tuple of elements, where is a non-negative integer. There is o ...
s of finite-field entries, and so tend to be called 'vectors' in descriptions of the algorithm.
The block Lanczos algorithm is amongst the most efficient methods known for finding nullspaces, which is the final stage in
integer factorization
In mathematics, integer factorization is the decomposition of a positive integer into a product of integers. Every positive integer greater than 1 is either the product of two or more integer factors greater than 1, in which case it is a comp ...
algorithms such as the
quadratic sieve and
number field sieve, and its development has been entirely driven by this application.
It is based on, and bears a strong resemblance to, the
Lanczos algorithm
The Lanczos algorithm is an iterative method devised by Cornelius Lanczos that is an adaptation of power iteration, power methods to find the m "most useful" (tending towards extreme highest/lowest) eigenvalues and eigenvectors of an n \times n ...
for finding
eigenvalue
In linear algebra, an eigenvector ( ) or characteristic vector is a vector that has its direction unchanged (or reversed) by a given linear transformation. More precisely, an eigenvector \mathbf v of a linear transformation T is scaled by a ...
s of large sparse real matrices.
Parallelization issues
The algorithm is essentially not parallel: it is of course possible to distribute the matrix–'vector' multiplication, but the whole vector must be available for the combination step at the end of each iteration, so all the machines involved in the calculation must be on the same fast network. In particular, it is not possible to widen the vectors and distribute slices of vectors to different independent machines.
The
block Wiedemann algorithm is more useful in contexts where several systems each large enough to hold the entire matrix are available, since in that algorithm the systems can run independently until a final stage at the end.
References
{{linear-algebra-stub
Numerical linear algebra