Re: ILU, bicgstab,cgs,bcg and time optimalization

[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