[petsc-users] MatOrdering for rectangular matrix

[Marcel Huysegoms]

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 
> <m.huysegoms at fz-juelich.de <mailto:m.huysegoms at fz-juelich.de>> 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/>

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.mcs.anl.gov/pipermail/petsc-users/attachments/20201022/206c8d5e/attachment-0001.html>