CFD Online Logo CFD Online URL
www.cfd-online.com
[Sponsors]
Home > Forums > Software User Forums > OpenFOAM

Why renumbering works for LduMatrix?

Register Blogs Members List Search Today's Posts Mark Forums Read

Reply
 
LinkBack Thread Tools Display Modes
Old   July 30, 2017, 11:16
Arrow Why renumbering works for LduMatrix?
  #1
Member
 
Di Cheng
Join Date: May 2010
Location: Beijing, China
Posts: 45
Rep Power: 10
chengdi is on a distinguished road
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?
chengdi is offline   Reply With Quote

Old   July 31, 2017, 02:55
Default
  #2
Senior Member
 
Hrvoje Jasak
Join Date: Mar 2009
Location: London, England
Posts: 1,823
Rep Power: 27
hjasak will become famous soon enough
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
hjasak is offline   Reply With Quote

Old   July 31, 2017, 04:22
Default
  #3
Member
 
Di Cheng
Join Date: May 2010
Location: Beijing, China
Posts: 45
Rep Power: 10
chengdi is on a distinguished road
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?
chengdi is offline   Reply With Quote

Old   July 31, 2017, 10:28
Default
  #4
Senior Member
 
Hrvoje Jasak
Join Date: Mar 2009
Location: London, England
Posts: 1,823
Rep Power: 27
hjasak will become famous soon enough
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
hjasak is offline   Reply With Quote

Old   July 31, 2017, 18:54
Default
  #5
Member
 
Di Cheng
Join Date: May 2010
Location: Beijing, China
Posts: 45
Rep Power: 10
chengdi is on a distinguished road
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.
chengdi is offline   Reply With Quote

Reply

Tags
openfoam, renumbering

Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are On


Similar Threads
Thread Thread Starter Forum Replies Last Post
[GAMBIT] Gambit works on Windows, but not in Linux victorz ANSYS Meshing & Geometry 8 April 14, 2013 20:40
Multiple Installation Issue: Parallel Processing No Longer Works dancfd OpenFOAM Installation 7 February 17, 2012 04:57
git problem: 1.7.x works but 1.6.x not af631717 OpenFOAM Installation 2 August 23, 2010 05:22
how fluent works asim ibrahim Main CFD Forum 13 October 6, 2006 03:59
ARTICLES AND WORKS CONCERNING CFD OF LIQUID-LIQUID DISPERSION AND DROPS SIZE IN AGITATED SYSTEMS.. tim Main CFD Forum 1 June 22, 1999 08:07


All times are GMT -4. The time now is 02:55.