[Octave-bug-tracker] [bug #53140] Solution of a system of linear equations takes forever and hurts OS performance.

[Marco Caliari]

Follow-up Comment #18, bug #53140 (project octave):

Since b is sparse with 9 elements different from zero per column, on average,
I thought that a problematic part was


for (octave_idx_type j = 0; j < b_nc; j++)
  {
    for (octave_idx_type i = 0; i < b_nr; i++)
      Bx[i] = b.elem (i, j);
    status = UMFPACK_DNAME (solve) (UMFPACK_A, Ap,
                                    Ai, Ax, Xx, Bx, Numeric,
                                    control, info);


and replaced it with


for (octave_idx_type i = 0; i < b_nr; i++)
  Bx[i] = 0.0;
for (octave_idx_type j = 0; j < b_nc; j++)
  {
    for (octave_idx_type i = b.cidx(j); i < b.cidx(j+1); i++)
      Bx[b.ridx(i)] = b.data(i);
    status = UMFPACK_DNAME (solve) (UMFPACK_A, Ap,
                                    Ai, Ax, Xx, Bx, Numeric,
                                    control, info);
    for (octave_idx_type i = b.cidx(j); i < b.cidx(j+1); i++)
      Bx[b.ridx(i)] = 0.0;


with no gain at all. Then I read


When you have many linear systems to solve, this routine [umfpack_*_wsolve] is
faster than umfpack_*_solve, since the workspace (Wi, W) needs to be allocated
only once, prior to calling umfpack_*_wsolve.


and replaced the orignal code with


for (octave_idx_type j = 0; j < b_nc; j++)
  {
    for (octave_idx_type i = 0; i < b_nr; i++)
      Bx[i] = b.elem (i, j);
    status = UMFPACK_DNAME (wsolve) (UMFPACK_A, Ap,
                                    Ai, Ax, Xx, Bx, Numeric,
                                    control, info, Wi, W);


where


OCTAVE_LOCAL_BUFFER (octave_idx_type, Wi, b_nr);
OCTAVE_LOCAL_BUFFER (double, W, b_nr);


In this way I can reduce the solution A\b from about 60 seconds to about 40
seconds. Comments before I prepare a patch?


    _______________________________________________________

Reply to this item at:

  <http://savannah.gnu.org/bugs/?53140>

_______________________________________________
  Message sent via/by Savannah
  http://savannah.gnu.org/