ILU, bicgstab,cgs,bcg and time optimalization

[R!]

Hi,

I sent you some procedure  last months. I hope that i will send two more (bcg and ILU). But I also have some questions to you, mainly connected with speed of these procedures.

I noticed that now they are terribly slow, I tracked the problem and I have found that it 's due to these functions which I'm currently using
cond() - is really really very slow on sparse matrix on which this function is used, when checking if preconditioner isn't ill-conditioned so I think that I can remove it quite safely (and rely on user that will give me good preconditioner)

Next weak point is inv function currently I'm calling inv on my preconditioner. I hoped that it will speedup my algorithm little bit(in next cycle I can use multipy insted of divide with my preconditioner), but in fact the inv procedure takes so much time that its rather drawback.


Another problem  which I have is with ILU. Now I'm comuting ILU and MILU (column modification) My function currenty has the same Params as matlab but some of them I'm ignoring and I'm affraid that I will not be able to implement them in near future.  But these procedure is really sllow.the  main problem is this

function auto(A)
    for i=1:5000 is
        v = A(i,i)+i*i;
    endfor
endfunction
this simple function takes about 0,2s on my PC but in matlab it takes about 0,002s. I think  that it the reason why my ilu procedure takes about 10 minutes to compute L U factors on matrix with 5000 rows. I'm not sure if it's useful in this time and Will this procedure be a benefit for octave ?

Have got any suggestion or advice for me?

Thanks

[Jason Riedy]

And R. ! writes:
> I noticed that now they are terribly slow, I tracked the problem and I have
> found that it 's due to these functions which I'm currently using
> cond() - is really really very slow on sparse matrix on which this function
> is used, [...]

Octave now has condest, which is much faster.  But, as you note,
hopefully not necessary.

> Next weak point is inv function currently I'm calling inv on my
> preconditioner.

That changes the numerical behavior substantially as well as
performance.  See research on the AINV (approximate inverse)
preconditioner for numerical issues.  And for performance, the inverse
of sparse blocks typically are dense.  That's not what you want.  Stick
with solves by the preconditioner's factors *if* that's the type of
preconditioner you're using.  Preconditioners typically are designed to
have "easy" factorizations and fast (very sparse) solves.

Your example code is not at all vectorized.  Matlab(TM) has a JIT
compilation system now, so it can cope with some of these loops.

Since your example code doesn't really do anything, I'll add a piece to
compute a vector v:
> for i=1:5000 is
>   v(i) = A(i,i)+i*i;
     ^^^ added
> endfor

Compare the runtime of the above loop to
  v = diag (A) + (1:5000).^2;

BTW, if you really want a high-performance ILU factorization for Octave,
you want to look into native code.  UMFPACK, already used in Octave, has
a drop tolerance you can use for a simple ILU variant.

More complicated ILU preconditioners could be built from LLNL's hypre
library.  It is now under the GPL (v2.1) and thus may be compatible with
GNU Octave.  It appears to be under active development again, and may
not run into errors every time there's a slight breeze:
  https://computation.llnl.gov/casc/linear_solvers/sls_hypre.html
And, of course, there's always PETSc:
  http://www.mcs.anl.gov/petsc/

Generally, performance of sparse codes what work on the matrix's
structure directly in Octave's language is not so great.  You eat a lot
of interpreter overhead or your code is so convoluted that it's not
worth avoiding C++ / Fortran.  Performance of codes that use higher
level building blocks (matrix-vector product, factorization, etc.) is
just fine.

Jason