Solving linear systems by Wiedemann's algorithm
This functionality does not run in MATLAB.
linalg::wiedemann(A, b, mult, ...) tries
to find a vector
satisfies the equation
using Wiedemann's algorithm.
mult must be a function such
that the result of
y is of the same domain type as
mult does not need to handle other
types of parameters, nor does it need to handle other matrices than
linalg::wiedemann uses a probabilistic algorithm.
For a deterministic variant enter
FALSE for the
If the system
not have a solution, then
If the system has more than one solution, then a random one is returned.
Due to the probabilistic nature of Wiedemann's algorithm, the
computation may fail with small probability. In this case
returned. If the deterministic variant is chosen, then the algorithm
may be slower for a small number of matrices.
b must be defined over the component
The coefficient ring of
A must be a field,
i.e., a domain of category
It is recommended to use
mult uses significantly less than O(n2) field
We define a matrix and a column vector over the finite field with 29 elements:
MatZ29 := Dom::Matrix(Dom::IntegerMod(29)): A := MatZ29([[1, 2, 3], [4, 7, 8], [9, 12, 17]]); b := MatZ29([1, 2, 3])
A does not have a special form that
would allow a fast matrix-vector multiplication, we simply use
Wiedemann's algorithm works in this case, although it is less efficient
than Gaussian elimination:
linalg::wiedemann(A, b, _mult)
Now let us define another matrix that has a special form:
MatZ29 := Dom::Matrix(Dom::IntegerMod(29)): A := MatZ29([[1, 0, 0], [0, 1, 2], [0, 0, 1]]); b := MatZ29(3, 1, [1, 2, 3]):
For this particular matrix, it is easy to define an efficient multiplication method:
mult := proc(dummy, y) begin y:=y+2*y; y end: linalg::wiedemann(A, b, mult)
An n×n matrix
of a domain of category
column vector, i.e., an n×1 matrix
of a domain of category
A matrix-vector multiplication method: function or functional
Either the list
[x, TRUE] if a solution for
been found, or the list
[x, FALSE] if a non-zero
solution for the corresponding homogeneous system
been found, or the value
FAIL (see below).
The expected running time for the probabilistic algorithm is O(n2 + n M),
and the running time for the deterministic variant is O(n2 M) in
the worst case, but only O(n2 + n M) on
average. Here, M is
the number of field operations that the matrix-vector multiplication
The basic idea of the algorithm is to solve a linear system by finding the minimal polynomial f(y) that solves . If the constant coefficient c = f(0) is non-zero and g(y) := f(y) - c, the equality implies that is the solution.
The polynomial f is found by looking for the minimal polynomial h satisfying for some randomly chosen row vector . This may yield h ≠ f in unlucky cases, but in general the probability for this is small.
 Douglas Wiedemann: "Solving Sparse Linear equations over Finite Fields", IEEE Transactions on Information Theory, vol. 32, no.1, Jan. 1986.