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
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
(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)
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/>
