> < ^ Date: Thu, 03 Feb 2000 11:53:53 +1000 (EST)
> ^ From: Greg Gamble <greg.gamble@math.rwth-aachen.de >
> < ^ Subject: Re: gauss algorithm
On Wed, 2 Feb 2000, Kurt Ewald wrote:
> Dear forum,
> I have written a program for the gauss algorithm, but it will run at the
> second call:
> gap> gauss:=function(A,m,n)
>*> local i,j,k,rcharind,B;
> > k:=1;r:=0;charind:=[];
> > repeat
> >    for j in [1..n] do
> >         if A[k][j]=0 then
> >             for i in [k+1..m] do
> >                 if A[i][j]<>0 then
> >                     B:=A[i];A[i]:=A[k];A[k]:=B;
> >                     break;
> >                 fi;
> >             od;
> >         fi;
> >         if A[k][j]<>0 then
> >            r:=r+1;Add(charind,j);
> >            A[k]:=A[k]*1/A[k][j];
>*>            for i in [k+1,m] do
> >                 A[i]:=A[i]+A[k]*-A[i][j];
> >            od;
> >            k:=k+1;
> >         fi;
> >    od;
> > until k=m;
> > for k in [2..r] do
> >    for i in [1..k-1] do
> >       A[i]:=A[i]+A[k]*-A[i][charind[k]];
> >    od;
> > od;
> > end;
> function( A, m, n ) ... end

Dear Kurt,

Besides the typo. introduced on the first line *-ed above ...

> local i,j,k,rcharind,B;
^
(you need a comma between r and charind), your problem lies on
the second line *-ed ...

>            for i in [k+1,m] do
                          ^
(the comma should be ..) i.e. the line should read:
for i in [k+1..m] do

since k+1 can be larger than m and, as with your example, lead
to indexing beyond the bounds of the matrix. Continuing with your
example (except I've prettied it up):

gap> A:=[ [ 1,-1, 1, 1, 1, 2 ], 
          [ 0, 1, 2, 1, 5, 9 ], 
          [ 0, 0, 0, 1, 2, 3 ],
          [ 0, 1, 2,-2,-1, 0 ], 
          [ 0, 0, 0, 1, 2,-3 ] ];
[ [ 1, -1, 1, 1, 1, 2 ], [ 0, 1, 2, 1, 5, 9 ], [ 0, 0, 0, 1, 2, 3 ],
  [ 0, 1, 2, -2, -1, 0 ], [ 0, 0, 0, 1, 2, -3 ] ]

gap> gauss(A,5,6);

List Element: <list>[6] must have an assigned value at
A[i] := A[i] + A[k] * - A[i][j];
<function>( <arguments> ) called from read-eval-loop
Entering break read-eval-print loop, you can 'quit;' to quit to outer loop,
or you can return after assigning a value to continue

Now GAP has alerted precisely that i is larger than the bounds of the
matrix. One of the nice features of GAP is that in the break loop one
can query GAP for the values of all the variables at the time the
error was detected ... the variables of interest at this line of your
function are i, j, k, m and A ... so let's see what they are:

brk> i;
6
brk> j;
6
brk> k;
5
brk> m;
5
brk> A;
[ [ 1, -1, 1, 1, 1, 2 ], [ 0, 1, 2, 1, 5, 9 ], 
  [ 0, 1/2, 1, -1, -1/2, 0 ], [ 0, 0, 0, 1, 2, 3 ], 
  [ 0, 0, 0, 0, 0, 1 ] ]

As you can see i = 6 > 5 = m giving rise to the error message
given. Now if you quit the break loop and try again:

brk> quit; 
gap> gauss(A,5,6);

the A you are using has been partially reduced i.e. it is not
the same A you started with ... and it just happens that with
this A the bug in your function is not a problem and you do
end up with a correctly Gauss-Jordan reduced matrix.

Observe that in your function you make use of the fact that
if the first index `a' of a list of form [a..b] is larger than
the second index `b' then the result is an empty list. So
[k+1..m] (correctly) evaluates to the empty list at the point the
error occurred above.

  Regards,
  Greg Gamble
___________________________________________________________________
Greg Gamble   __________________        mailto:gregg@csee.uq.edu.au
Centre for Discrete Mathematics & Computing    Tel: +61-7 336 52425
Department of Computer Science                 Fax: +61-7 336 54999
      & Electrical Engineering     http://www.csee.uq.edu.au/~gregg
The University of Queensland, Queensland 4072 AUSTRALIA
___________________________________________________________________

> < [top]