Timeline for How to reorder variables to produce a banded matrix of minimum bandwidth?
Current License: CC BY-SA 3.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 27, 2012 at 16:18 | history | edited | Jack Poulson | CC BY-SA 3.0 |
Adding citations for the connection between MeTiS and Chaco.
|
| Aug 27, 2012 at 16:11 | history | edited | Jack Poulson | CC BY-SA 3.0 |
Hendrickson (one of the authors of Chaco) wrote a paper on multi-level approaches which was cited as the starting point for the main MeTiS paper.
|
| Aug 27, 2012 at 13:59 | comment | added | Jed Brown | @Alexander Everyone attributes the 3D bound to George and Liu, though I don't know if they explicitly point it out in the book. It is obvious from the theory however. The minimal vertex separator for a $n = m\times m\times m$ grid is $n^{2/3} = m\times m$. The dense matrix associated with that supernode has $(n^{2/3})^2 = n^{4/3}$ entries and requires $(n^{2/3})^3 = n^2$ operations to factor. The logarithmic term in the 2D case is more subtle and is treated in Chapter 8 on Nested Dissection, which achieves the lower bound. | |
| Aug 27, 2012 at 8:55 | comment | added | Alexander | @JedBrown I've been trying to find claimed bounds in cited book, but couldn't do that. Specifically for 3D case. Could you please point more precisely where are they there? Thank you. | |
| Jan 19, 2012 at 19:51 | vote | accept | Paul | ||
| Jan 19, 2012 at 5:34 | comment | added | Paul | @JedBrown That was a great reference! Thanks so much! :) | |
| Jan 18, 2012 at 20:56 | comment | added | Jed Brown | I updated the link to point to the PDF of the book instead of the book review. | |
| Jan 18, 2012 at 20:55 | history | edited | Jed Brown | CC BY-SA 3.0 |
Link to George and Liu's book
|
| Jan 18, 2012 at 19:04 | comment | added | Jack Poulson | Added; I was about to get out of the car when I first submitted it. I know that there exists a freely available version of the book online somewhere (Jed knows where it is), but I could not find it. | |
| Jan 18, 2012 at 19:03 | history | edited | Jack Poulson | CC BY-SA 3.0 |
Added link to George and Liu book, and more discussion of Chaco.
|
| Jan 18, 2012 at 18:49 | comment | added | Paul | Do you have a citation for the George and Liu reference? | |
| Jan 18, 2012 at 18:26 | history | answered | Jack Poulson | CC BY-SA 3.0 |