linalg::wiedemann

Solving linear systems by Wiedemann's algorithm

Use only in the MuPAD Notebook Interface.

This functionality does not run in MATLAB.

Syntax

linalg::wiedemann(A, b, <mult>, <prob>)

Description

linalg::wiedemann(A, b, mult, ...) tries to find a vector that satisfies the equation by using Wiedemann's algorithm.

The parameter mult must be a function such that the result of mult(A,y) equals for every n-dimensional column vector . The parameter y is of the same domain type as A. The argument mult does not need to handle other types of parameters, nor does it need to handle other matrices than A.

linalg::wiedemann uses a probabilistic algorithm. For a deterministic variant enter FALSE for the optional parameter prob.

If the system does not have a solution, then linalg::wiedemann returns FAIL.

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 FAIL is returned. If the deterministic variant is chosen, then the algorithm may be slower for a small number of matrices.

The vector b must be defined over the component ring of A.

The coefficient ring of A must be a field, i.e., a domain of category Cat::Field.

It is recommended to use linalg::wiedemann only if mult uses significantly less than O(n2) field operations.

Examples

Example 1

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])

Since A does not have a special form that would allow a fast matrix-vector multiplication, we simply use _mult. Wiedemann's algorithm works in this case, although it is less efficient than Gaussian elimination:

linalg::wiedemann(A, b, _mult)

Example 2

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[2]:=y[2]+2*y[3];
    y
end:
linalg::wiedemann(A, b, mult)

Parameters

A

An n×n matrix of a domain of category Cat::Matrix

b

An n-dimensional column vector, i.e., an n×1 matrix of a domain of category Cat::Matrix

mult

A matrix-vector multiplication method: function or functional expression; default: _mult

prob

TRUE or FALSE (default: TRUE)

Return Values

Either the list [x, TRUE] if a solution for the system has been found, or the list [x, FALSE] if a non-zero solution for the corresponding homogeneous system has been found, or the value FAIL (see below).

Algorithms

The expected running time for the probabilistic algorithm is O(n2 + nM), and the running time for the deterministic variant is O(n2M) in the worst case, but only O(n2 + nM) on average. Here, M is the number of field operations that the matrix-vector multiplication routine mult uses.

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 hf in unlucky cases, but in general the probability for this is small.

References

[1] Douglas Wiedemann: "Solving Sparse Linear equations over Finite Fields", IEEE Transactions on Information Theory, vol. 32, no.1, Jan. 1986.

Was this topic helpful?