linalg::wiedemann -- solving
linear systems by Wiedemann's algorithm
Introductionlinalg::wiedemann(A, b, mult ...) tries to
find a vector x that satisfies the equation A*x =
b by using Wiedemann's algorithm.
Call(s)linalg::wiedemann(A, b <, mult>)
linalg::wiedemann(A, b <, mult>, prob)
ParametersA |
- | an n x n matrix of a domain of category
Cat::Matrix |
b |
- | an n-dimensional column vector, i.e., an
n x 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) |
Returnseither the list [x, TRUE] if a solution for the system
A*x=b has been found, or the list [x, FALSE] if
a non-zero solution for the corresponding homogeneous system
A*x=0 has been found, or the value FAIL (see
below).
Related
Functionslinalg::matlinsolve, linalg::vandermondeSolve
Detailsmult must be a function such that the
result of mult(A,y) equals A*y for every
n-dimensional column vector y. 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.linalg::wiedemann returns FAIL.FAIL is 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 ring
of A.A must be a field, i.e., a
domain of category Cat::Field.linalg::wiedemann only if
mult uses significantly less than O(n^2) field
operations.
Example
1We 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])
+- -+
| 1 mod 29, 2 mod 29, 3 mod 29 |
| |
| 4 mod 29, 7 mod 29, 8 mod 29 |
| |
| 9 mod 29, 12 mod 29, 17 mod 29 |
+- -+
+- -+
| 1 mod 29 |
| |
| 2 mod 29 |
| |
| 3 mod 29 |
+- -+
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)
-- +- -+ --
| | 24 mod 29 | |
| | | |
| | 21 mod 29 |, TRUE |
| | | |
| | 17 mod 29 | |
-- +- -+ --
Example
2Now 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]):
+- -+
| 1 mod 29, 0 mod 29, 0 mod 29 |
| |
| 0 mod 29, 1 mod 29, 2 mod 29 |
| |
| 0 mod 29, 0 mod 29, 1 mod 29 |
+- -+
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)
-- +- -+ --
| | 1 mod 29 | |
| | | |
| | 25 mod 29 |, TRUE |
| | | |
| | 3 mod 29 | |
-- +- -+ --
Backgroundmult uses.The polynomial f is found by looking for the minimal polynomial h satisfying u h(A) b = 0 for some randomly chosen row vector u. This may yield h ≠f in unlucky cases, but in general the probability for this is small.