computer science Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...

, the block Lanczos algorithm is an

algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...

for finding the

nullspace In mathematics, the kernel of a linear map, also known as the null space or nullspace, is the linear subspace of the domain of the map which is mapped to the zero vector. That is, given a linear map between two vector spaces and , the kernel of ...

of a

matrix Matrix most commonly refers to: * ''The Matrix'' (franchise), an American media franchise ** ''The Matrix'', a 1999 science-fiction action film ** "The Matrix", a fictional setting, a virtual reality environment, within ''The Matrix'' (franchis ...

over a

finite field In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field that contains a finite number of elements. As with any field, a finite field is a set on which the operations of multiplication, addition, subtr ...

, 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 ordered list (sequence) of elements. An -tuple is a sequence (or ordered list) of elements, where is a non-negative integer. There is only one 0-tuple, referred to as ''the empty tuple''. An -tuple is defi ...

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 number theory, integer factorization is the decomposition of a composite number into a product of smaller integers. If these factors are further restricted to prime numbers, the process is called prime factorization. When the numbers are suf ...

algorithms such as the

quadratic sieve The quadratic sieve algorithm (QS) is an integer factorization algorithm and, in practice, the second fastest method known (after the general number field sieve). It is still the fastest for integers under 100 decimal digits or so, and is considerab ...

and

number field sieve In number theory, the general number field sieve (GNFS) is the most efficient classical algorithm known for factoring integers larger than . Heuristically, its complexity for factoring an integer (consisting of bits) is of the form :\exp\left( ...

, 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 of a linear transformation is a nonzero vector that changes at most by a scalar factor when that linear transformation is applied to it. The corresponding eigenvalue, often denoted b ...

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 The block Wiedemann algorithm for computing kernel vectors of a matrix over a finite field is a generalization by Don Coppersmith of an algorithm due to Doug Wiedemann. Wiedemann's algorithm Let M be an n\times n square matrix over some fi ...

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