# 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.