Can someone recommend a mature and robust grid reordering algorithm?

Sheldon Lee · January 14, 2015, 09:49

I am developing a LU-SGS code now, and is searching for a appropriate reordering method.

Is there anybody with rich experience of grid rerodering ?

many thank!

mprinkey · January 14, 2015, 13:41

I've done grid re-ordering with Reverse Cuthill-McKee. Also, I've done it (along with parallel partitioning) using Hilbert Space Filling curves. The former uses only graph information, while the latter uses geometric data. And, as chance would have it, I was reading this paper last night:

http://www.jpier.org/PIERL/pierl09/04.09042305.pdf

RCM seems to be the most commonly used. The GPS scheme and variants in the paper are less robust but deliver better reduction. Space-filling curves come at the problem from a different direction, but can be quite useful, especially if you need to sort cells, faces, edges, and/or nodes to access all of them together efficiently.

EDIT. I should also note that space-filling curves may not always provide absolute minimum bandwidth. They tend to give good bandwidth reduction on most rows with a handful of outliers that could have large bandwidth. For cache optimization, it still works reasonably well...a few misses will always occur and so it is more the average cache hit rate that matters in those situations. But for schemes that do require absolute reduction (say to prevent large amounts of fill-in for direct solvers), RCM or GPS are a better choice.

Sheldon Lee · January 20, 2015, 04:38

have you used the RCM method along with the lu-sgs or gmres? Is the effect obvious?

Quote:

Originally Posted by mprinkey

I've done grid re-ordering with Reverse Cuthill-McKee. Also, I've done it (along with parallel partitioning) using Hilbert Space Filling curves. The former uses only graph information, while the latter uses geometric data. And, as chance would have it, I was reading this paper last night:

http://www.jpier.org/PIERL/pierl09/04.09042305.pdf

RCM seems to be the most commonly used. The GPS scheme and variants in the paper are less robust but deliver better reduction. Space-filling curves come at the problem from a different direction, but can be quite useful, especially if you need to sort cells, faces, edges, and/or nodes to access all of them together efficiently.

EDIT. I should also note that space-filling curves may not always provide absolute minimum bandwidth. They tend to give good bandwidth reduction on most rows with a handful of outliers that could have large bandwidth. For cache optimization, it still works reasonably well...a few misses will always occur and so it is more the average cache hit rate that matters in those situations. But for schemes that do require absolute reduction (say to prevent large amounts of fill-in for direct solvers), RCM or GPS are a better choice.

mprinkey · January 20, 2015, 15:10

Sorry, no. I've never done anything with lu-sgs. I've use GMRES for linear systems, but never with grid re-ordering.

January 14, 2015, 09:49	Can someone recommend a mature and robust grid reordering algorithm?	#1
Sheldon Lee New Member Sheldon Lee Join Date: May 2014 Location: On the moon. Posts: 11 Rep Power: 12	I am developing a LU-SGS code now, and is searching for a appropriate reordering method. Is there anybody with rich experience of grid rerodering ? many thank!

January 14, 2015, 13:41		#2
mprinkey Senior Member Michael Prinkey Join Date: Mar 2009 Location: Pittsburgh PA Posts: 363 Rep Power: 25	I've done grid re-ordering with Reverse Cuthill-McKee. Also, I've done it (along with parallel partitioning) using Hilbert Space Filling curves. The former uses only graph information, while the latter uses geometric data. And, as chance would have it, I was reading this paper last night: http://www.jpier.org/PIERL/pierl09/04.09042305.pdf RCM seems to be the most commonly used. The GPS scheme and variants in the paper are less robust but deliver better reduction. Space-filling curves come at the problem from a different direction, but can be quite useful, especially if you need to sort cells, faces, edges, and/or nodes to access all of them together efficiently. EDIT. I should also note that space-filling curves may not always provide absolute minimum bandwidth. They tend to give good bandwidth reduction on most rows with a handful of outliers that could have large bandwidth. For cache optimization, it still works reasonably well...a few misses will always occur and so it is more the average cache hit rate that matters in those situations. But for schemes that do require absolute reduction (say to prevent large amounts of fill-in for direct solvers), RCM or GPS are a better choice. Last edited by mprinkey; January 15, 2015 at 01:09.

January 20, 2015, 15:10		#4
mprinkey Senior Member Michael Prinkey Join Date: Mar 2009 Location: Pittsburgh PA Posts: 363 Rep Power: 25	Sorry, no. I've never done anything with lu-sgs. I've use GMRES for linear systems, but never with grid re-ordering.