Subject: Defects in lu_factor() for degenerated matrices
From: vladimir voloshinov
Date: Fri, 26 Aug 2011 21:03:05 +0400
We have a long success story of Maxima usage.
But recently some unpleasant drawback had been found.
Current implementation of LU decomposition, lu_factor() function,
presented in linearalgebra pack has a number
of defects revealing for degenerated matrices.
Can somebody help, recommend a workaround or some other implementation
of lu_factor?
Take for example, a simplest 2x2 matrix:
M10_00:matrix([1,0],[0,0]);
[ 1 0 ]
[ 0 0 ]
and a permutation one:
Q:matrix([0,1],[1,0]);
[ 0 1 ]
[ 1 0 ]
Matrix M10_00 is factored correctly
[A:M10_00, get_lu_factors(lu_factor(A))];
[ 1 0 ] [ 1 0 ] [ 1 0 ] [ 1 0 ]
[ 0 0 ], [ 0 1 ] [ 0 1 ] [ 0 0 ]
But permuted matrix:
M10_00.Q;
[ 0 1 ]
[ 0 0 ]
causes an error in lu_factor():
[A:M10_00.Q, get_lu_factors(lu_factor(A))];
Unable to compute the LU factorization
-- an error. To debug this try: debugmode(true);
Obviously, that the reason is that
%MAXIMA_HOME%\share\maxima\5.24.0\share\linearalgebra\lu.lisp
does not implement "full pivoting" ("true" LU-factoring) when M is
represented as M=P.L.U.Q,
where P and Q are permutation matrices...
More over, Q.M10_00 is factored:
[A:Q.M10_00,get_lu_factors(lu_factor(A))];
[ 0 0 ] [ 0 1 ] [ 1 0 ] [ 1 0 ]
[ 1 0 ], [ 1 0 ] [ 0 1 ] [ 0 0 ]
but 3x3 matrix with two leading zero-rows is not (?!):
M000_000_100:matrix([0,0,0],[0,0,0],[1,0,0]);
[A:M000_000_100,get_lu_factors(lu_factor(A))];
Unable to compute the LU factorization
-- an error. To debug this try: debugmode(true);
We'll be thankful for any help!
Regards,
--
Vladimir V. Voloshinov,
Center of Grid-technologies & Distributed Computing, http://dcs.isa.ru,
Institute for System Analysis Russ. Acad. Sci., http://www.isa.ru,
web: http://dcs.isa.ru/wiki/staff/vladimirv