Marcel, He also has SuiteSparseQR AMD, so with your interpretation this means AMD can also reorder a rectangular matrix?
I think you need to dig into SuiteSparseQR or his papers to find out what he is actually reordering; I suspect it is not actually the rectangular matrix. Barry > On Oct 22, 2020, at 9:38 AM, Marcel Huysegoms <[email protected]> > wrote: > > Hi Matt, > > thanks for your response! > I haven't studied the recent literature on reordering algorithms, but came > across a talk by Tim Davis, the developer of SuiteSparse, from 2013: > > https://www.youtube.com/watch?v=7ph4ZQ9oEIc&t=2109s > <https://www.youtube.com/watch?v=7ph4ZQ9oEIc&t=2109s> > > At minute 33:40 he shows the impact of different reordering libraries applied > to a large least square system. > In doing so, he demonstrates how he achieves a significant speedup when using > the matrix reordering algorithm of METIS/ParMETIS (which is a multilevel > nested dissection). So it seems that METIS is able to compute an effective > column reordering of rectangular matrices for fill-reducing factorizations. > The respective slide of the talk is also available as a screenshot under: > > https://www.mathworks.com/matlabcentral/answers/uploaded_files/173888/image.png > > <https://www.mathworks.com/matlabcentral/answers/uploaded_files/173888/image.png> > > (extracted from a forum post on a similar topic: > https://de.mathworks.com/matlabcentral/answers/275622-large-sparse-rectangular-over-determined-equation-system-to-reorder-or-to-not-reorder > > <https://de.mathworks.com/matlabcentral/answers/275622-large-sparse-rectangular-over-determined-equation-system-to-reorder-or-to-not-reorder>) > > Considering that PETSc is offering a wrapper to the partitioning > functionalities of ParMETIS, I am wondering, if it might be reasonable in the > near future to also provide an option to use the reordering functionality of > METIS (METIS_NodeND/ParMETIS_V3_NodeND) from within PETSc? That would be > incredible and may be useful to many applications. I've just seen that > MatGetOrdering() even provides an option for external libraries > (MATORDERINGEXTERNAL). Is it maybe already possible to use the function in > conjuction with ParMETIS? > > Best regards, > Marcel > > > Am 22.10.20 um 11:55 schrieb Matthew Knepley: >> On Thu, Oct 22, 2020 at 4:24 AM Marcel Huysegoms <[email protected] >> <mailto:[email protected]>> wrote: >> Hi all, >> >> I'm currently implementing a Gauss-Newton approach for minimizing a >> non-linear cost function using PETSc4py. >> The (rectangular) linear systems I am trying to solve have dimensions of >> about (5N, N), where N is in the range of several hundred millions. >> >> Due to its size and because it's an over-determined system, I use LSQR >> in conjunction with a preconditioner (which operates on A^T x A, e.g. >> BJacobi). >> Depending on the ordering of the unknowns the algorithm only converges >> for special cases. When I use a direct LR solver (as preconditioner) it >> consistently converges, but consumes too much memory. I have read in the >> manual that the LR solver internally also applies a matrix reordering >> beforehand. >> >> My question would be: >> How can I improve the ordering of the unknowns for a rectangular matrix >> (in order to converge also with iterative preconditioners)? If I use >> MatGetOrdering(), it only works for square matrices. Is there a way to >> achieve this from within PETSc4py? >> ParMETIS seems to be a promising framework for that task. Is it possible >> to apply its reordering algorithm to a rectangular PETSc-matrix? >> >> I would be thankful for every bit of advice that might help. >> >> We do not have any rectangular reordering algorithms. I think your first >> step is to >> find something in the literature that you think will work. >> >> Thanks, >> >> Matt >> >> Best regards, >> Marcel >> >> >> ------------------------------------------------------------------------------------------------ >> ------------------------------------------------------------------------------------------------ >> Forschungszentrum Juelich GmbH >> 52425 Juelich >> Sitz der Gesellschaft: Juelich >> Eingetragen im Handelsregister des Amtsgerichts Dueren Nr. HR B 3498 >> Vorsitzender des Aufsichtsrats: MinDir Volker Rieke >> Geschaeftsfuehrung: Prof. Dr.-Ing. Wolfgang Marquardt (Vorsitzender), >> Karsten Beneke (stellv. Vorsitzender), Prof. Dr.-Ing. Harald Bolt >> ------------------------------------------------------------------------------------------------ >> ------------------------------------------------------------------------------------------------ >> >> >> >> -- >> What most experimenters take for granted before they begin their experiments >> is infinitely more interesting than any results to which their experiments >> lead. >> -- Norbert Wiener >> >> https://www.cse.buffalo.edu/~knepley/ <http://www.cse.buffalo.edu/~knepley/> >
