Incomplete LU factorisation


#1

Hi,

I wonder if there is an incomplete LU factorization like ilu in MATLAB. It would be useful to speed up iterative solver for example.

Ultimately, a matrix free version would be incredibly useful.

Thank you for your help.


#2

I have implemented this in R before, I’ll give it a try in Julia


#3

Dense or sparse?

I have Julia implementation of a limited-memory sparse modified signed Cholesky here: https://github.com/JuliaSmoothOptimizers/LLDL.jl. The modifications allow to compute an incomplete factorization of any symmetric sparse matrix as L D L^T where L is unit lower triangular and D is diagonal and indefinite. (This isn’t Bunch-Kaufman.) The input matrix will be shifted if necessary until the incomplete factorization exists.

It may be possible to generalize it and make it do incomplete LU.


#4

That looks interesting. Any chance to get a “Matrix Free” version?


#5

What do you mean by that?


#6

I mean when you are only provided with a function that evaluates the linear operator on vectors.


#7

Typically, you need the explicit matrix if you want an incomplete factorization, were it only to compute proper row and column scaling. If you forgo the scaling, you could technically generate the matrix one column at a time but it will still cost you n operator-vector products in the end. That would require major changes to the code though.