Sparse lu factorization without column pivoting

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|

Sparse lu factorization without column pivoting

Marco Caliari-4
Dear all,

as you can see here

https://savannah.gnu.org/bugs/?func=detailitem&item_id=53390

Octave is not currently able to perform a sparse LU factorization without
column pivoting (that is L*U=A or L*U=P*A) in a reliable way. The problem is
that the implementation is based on UMFPACK and it is not possible to disable
column pivoting in UMFPACK. This was privately confirmed me by the author of
SuiteSparse. He also agreed to add a note in the next version of SuiteSparse,
since it was not completely clear from the current documentation (and it was the
origin of the wrong implementaion in Octave).
This is not a huge problem, in my opinion, since when the matrix A is sparse,
one should *always* allow for column pivoting (that is L*U=P*A*Q), since this
preserves the sparsity of L and U. And this works in Octave (based on UMFPACK).
Anyway, I think it is not difficult to fix this problem. In fact, the
incomplete LU factorization of 'ilutp' type (and options droptol=0, milu =
"off", udiag = false) is almost what we need for the job. I slightly modified
it (function ilu_tp in __ilu__.cc) and I got a working LU factorization without
column pivoting.
Such a procedure should now be called in libinterp/corefcn/lu.cc around line
205 (when nargout < 4). How to do that is beyond my capabilities and I need
help or advise.

Regards,

Marco

--
Dr. Marco Caliari
Dipartimento di Informatica
Universita` degli Studi di Verona
Ca' Vignal 2
Strada le Grazie 15
37134 VERONA

tel: +39 045 802 7904
fax: +39 045 802 7068

Le informazioni trasmesse sono intese soltanto per la persona o l'ente cui
sono indirizzate e possono avere contenuto confidenziale e/o riservato. La
visione, la trasmissione, la diffusione o altro uso delle informazioni di
cui sopra e` proibita a chiunque ad esclusione del legittimo destinatario.
Se avete ricevuto queste informazioni per errore, siete pregati di
contattare il mittente e cancellare il materiale ricevuto.

The information transmitted is intended only for the person or entity to
which it is addressed and may contain confidential and/or privileged
material. Any review, retransmission, dissemination or other use of, or
taking of any action in reliance upon, this information by persons or
entities other than the intended recipient is prohibited. If you received
this in error, please contact the sender and delete the material from any
computer.

Reply | Threaded
Open this post in threaded view
|

Re: Sparse lu factorization without column pivoting

Rik-4
On 05/04/2018 09:00 AM, [hidden email] wrote:
Subject:
Sparse lu factorization without column pivoting
From:
Marco Caliari [hidden email]
Date:
05/04/2018 05:07 AM
To:
[hidden email]
List-Post:
[hidden email]
Content-Transfer-Encoding:
7bit
Precedence:
list
MIME-Version:
1.0
Message-ID:
<20180504140752.696c600c@caliari-PC>
Content-Type:
text/plain; charset=US-ASCII
Message:
5

Dear all,

as you can see here

https://savannah.gnu.org/bugs/?func=detailitem&item_id=53390

Octave is not currently able to perform a sparse LU factorization without
column pivoting (that is L*U=A or L*U=P*A) in a reliable way. The problem is
that the implementation is based on UMFPACK and it is not possible to disable
column pivoting in UMFPACK. This was privately confirmed me by the author of
SuiteSparse. He also agreed to add a note in the next version of SuiteSparse,
since it was not completely clear from the current documentation (and it was the
origin of the wrong implementaion in Octave).
This is not a huge problem, in my opinion, since when the matrix A is sparse,
one should *always* allow for column pivoting (that is L*U=P*A*Q), since this
preserves the sparsity of L and U. And this works in Octave (based on UMFPACK).
Anyway, I think it is not difficult to fix this problem. In fact, the
incomplete LU factorization of 'ilutp' type (and options droptol=0, milu =
"off", udiag = false) is almost what we need for the job. I slightly modified
it (function ilu_tp in __ilu__.cc) and I got a working LU factorization without
column pivoting.
Such a procedure should now be called in libinterp/corefcn/lu.cc around line
205 (when nargout < 4). How to do that is beyond my capabilities and I need
help or advise.

I can help with the C++ code.  We can take this off the mailing list and you can e-mail me directly at [hidden email].

--Rik