Why renumbering works for LduMatrix?
 

AFAIK, renumbering works for sparse matrix to reduce its band width if it is stored as array of diagonals data structure. However, for lduMatrix format used by OpenFOAM, it seems meanlingless to use renumbering because it does not reduce the operations (at least for matrix-vector product) performed by the solvers.

From the point of view of linear algebra, reordering does not change the eigen value of matrix hence its condition number.

So I am confused that why renumbering works for LduMatrix?

We know that each algorithm is also working with data structure. For lduMatrix data structure, how can we find the optimality of its algorithm?

Hi,

You need to read up on iterative solvers. For direct solvers, ordering formally makes no difference, although what Gauss elimination does includes pivoting - which is the same as renumbering.

You get 2 benefits from renumbering: fixed point iterations work better because the updated neighborhood is richer; also, computers run faster because you increased the cache hit rate.

However in FVM, unlike FEM, the benefit isn't huge.

Hrv

Thanks for your explanation, I did not count the cache hit rate. Considering cache hit rate, the same amount of operations can be completed faster.

I am still little confused by the fixed point iterations. Think about a Gauss-Seidel iteration. x_new=inv(L+D)*U*x_old. You said "working better because the updated neighborhood is richer". Does it mean making eigen values of (inv(L+D)*U) smaller, though the eigen value set of (L+D+U) does not change during renumbering?

Please consult a book: cell renumbering and order of equations influences the performance of Guass-Seidel sweeps. Consider for example red-black renumbering, which reduces Gauss Seidel to (almost) point Jacobi sweep.

Reduced matrix band increases the number of equation neighbours that have already been visited, and thus influences the efficiency of the algorithm.

May I recommend the numerical linear algebra course I hold at Uni Zagreb.

Hrv

Thanks for your reply. But I cannot find the book, could you give me the ISBN or DOI? Or the webpage relating to your numerical linear algebra course. I am currently looking for algorithms which is extremely scalable and matrix free.

I can see the benefits of more updated neighbours. Just like the GS iteration is almost two times faster than Jacobi iteration because the spectrum of iterative matrix of GS iteration is half of Jacobi iteration and hence the residual decreases faster.

From viewpoint of information theory, more updated neighbour means faster horizontal broadcast of information. Higher cache hit rates also means higher vectical information transimission speed.

I am just curious about if there is some proof or experiment data about the acceleration factor of renumbering on both effects.

For unpreconditioned Krylov-type solver which only uses matrix-vector product, the renumbering should only benefits from increased cache hit rates. I will try to do some test on it.