Previous Page Contents

linalg::wiedemann -- solving linear systems by Wiedemann's algorithm

Introduction

linalg::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)

Parameters

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

Returns

either 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 Functions

linalg::matlinsolve, linalg::vandermondeSolve

Details

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

Background

Changes




Do you have questions or comments?


Copyright © SciFace Software GmbH & Co. KG 2000