|
[Sponsors] |
July 30, 2017, 12:16 |
Why renumbering works for LduMatrix?
|
#1 |
Member
Di Cheng
Join Date: May 2010
Location: Beijing, China
Posts: 47
Rep Power: 16 |
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? |
|
July 31, 2017, 03:55 |
|
#2 |
Senior Member
Hrvoje Jasak
Join Date: Mar 2009
Location: London, England
Posts: 1,907
Rep Power: 33 |
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
__________________
Hrvoje Jasak Providing commercial FOAM/OpenFOAM and CFD Consulting: http://wikki.co.uk |
|
July 31, 2017, 05:22 |
|
#3 |
Member
Di Cheng
Join Date: May 2010
Location: Beijing, China
Posts: 47
Rep Power: 16 |
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? |
|
July 31, 2017, 11:28 |
|
#4 |
Senior Member
Hrvoje Jasak
Join Date: Mar 2009
Location: London, England
Posts: 1,907
Rep Power: 33 |
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
__________________
Hrvoje Jasak Providing commercial FOAM/OpenFOAM and CFD Consulting: http://wikki.co.uk |
|
July 31, 2017, 19:54 |
|
#5 |
Member
Di Cheng
Join Date: May 2010
Location: Beijing, China
Posts: 47
Rep Power: 16 |
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. |
|
Tags |
openfoam, renumbering |
Thread Tools | Search this Thread |
Display Modes | |
|
|
Similar Threads | ||||
Thread | Thread Starter | Forum | Replies | Last Post |
[OpenFOAM.com] Multiple Installation Issue: Parallel Processing No Longer Works | dancfd | OpenFOAM Installation | 11 | November 20, 2018 17:08 |
[GAMBIT] Gambit works on Windows, but not in Linux | victorz | ANSYS Meshing & Geometry | 8 | April 14, 2013 21:40 |
git problem: 1.7.x works but 1.6.x not | af631717 | OpenFOAM Installation | 2 | August 23, 2010 06:22 |
how fluent works | asim ibrahim | Main CFD Forum | 13 | October 6, 2006 04:59 |
ARTICLES AND WORKS CONCERNING CFD OF LIQUID-LIQUID DISPERSION AND DROPS SIZE IN AGITATED SYSTEMS.. | tim | Main CFD Forum | 1 | June 22, 1999 09:07 |