<html><head><meta http-equiv="Content-Type" content="text/html; charset=us-ascii"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class=""><div class=""><br class=""></div><div class=""> Marcel,</div><div class=""><br class=""></div> He also has SuiteSparseQR AMD, so with your interpretation this means AMD can also reorder a rectangular matrix?<div class=""><br class=""></div><div class=""> 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.</div><div class=""><br class=""></div><div class=""> Barry</div><div class=""><br class=""><div class=""><br class=""></div><div class=""><br class=""><div><br class=""><blockquote type="cite" class=""><div class="">On Oct 22, 2020, at 9:38 AM, Marcel Huysegoms <<a href="mailto:m.huysegoms@fz-juelich.de" class="">m.huysegoms@fz-juelich.de</a>> wrote:</div><br class="Apple-interchange-newline"><div class="">
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8" class="">
<div class="">
Hi Matt,<br class="">
<br class="">
thanks for your response! <br class="">
I haven't studied the recent literature on reordering algorithms,
but came across a talk by Tim Davis, the developer of SuiteSparse,
from 2013:<br class="">
<br class="">
<a class="moz-txt-link-freetext" href="https://www.youtube.com/watch?v=7ph4ZQ9oEIc&t=2109s">https://www.youtube.com/watch?v=7ph4ZQ9oEIc&t=2109s</a><br class="">
<br class="">
At minute 33:40 he shows the impact of different reordering
libraries applied to a large least square system.<br class="">
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:<br class="">
<br class="">
<a class="moz-txt-link-freetext" href="https://www.mathworks.com/matlabcentral/answers/uploaded_files/173888/image.png">https://www.mathworks.com/matlabcentral/answers/uploaded_files/173888/image.png</a><br class="">
<br class="">
(extracted from a forum post on a similar topic:
<a class="moz-txt-link-freetext" href="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</a>)<br class="">
<br class="">
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?<br class="">
<br class="">
Best regards,<br class="">
Marcel<br class="">
<br class="">
<br class="">
<div class="moz-cite-prefix">Am 22.10.20 um 11:55 schrieb Matthew
Knepley:<br class="">
</div>
<blockquote type="cite" cite="mid:CAMYG4GmJT_uzAJXW10Z9BU3fGsGDrTZhRttKJa4Xts0Ow59dbQ@mail.gmail.com" class="">
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8" class="">
<div dir="ltr" class="">
<div dir="ltr" class="">On Thu, Oct 22, 2020 at 4:24 AM Marcel Huysegoms
<<a href="mailto:m.huysegoms@fz-juelich.de" moz-do-not-send="true" class="">m.huysegoms@fz-juelich.de</a>>
wrote:<br class="">
</div>
<div class="gmail_quote">
<blockquote class="gmail_quote" style="margin:0px 0px 0px
0.8ex;border-left:1px solid
rgb(204,204,204);padding-left:1ex">Hi all,<br class="">
<br class="">
I'm currently implementing a Gauss-Newton approach for
minimizing a<br class="">
non-linear cost function using PETSc4py.<br class="">
The (rectangular) linear systems I am trying to solve have
dimensions of<br class="">
about (5N, N), where N is in the range of several hundred
millions.<br class="">
<br class="">
Due to its size and because it's an over-determined system,
I use LSQR<br class="">
in conjunction with a preconditioner (which operates on A^T
x A, e.g.<br class="">
BJacobi).<br class="">
Depending on the ordering of the unknowns the algorithm only
converges<br class="">
for special cases. When I use a direct LR solver (as
preconditioner) it<br class="">
consistently converges, but consumes too much memory. I have
read in the<br class="">
manual that the LR solver internally also applies a matrix
reordering<br class="">
beforehand.<br class="">
<br class="">
My question would be:<br class="">
How can I improve the ordering of the unknowns for a
rectangular matrix<br class="">
(in order to converge also with iterative preconditioners)?
If I use<br class="">
MatGetOrdering(), it only works for square matrices. Is
there a way to<br class="">
achieve this from within PETSc4py?<br class="">
ParMETIS seems to be a promising framework for that task. Is
it possible<br class="">
to apply its reordering algorithm to a rectangular
PETSc-matrix?<br class="">
<br class="">
I would be thankful for every bit of advice that might help.<br class="">
</blockquote>
<div class=""><br class="">
</div>
<div class="">We do not have any rectangular reordering algorithms. I
think your first step is to</div>
<div class="">find something in the literature that you think will
work.</div>
<div class=""><br class="">
</div>
<div class=""> Thanks,</div>
<div class=""><br class="">
</div>
<div class=""> Matt</div>
<div class=""> </div>
<blockquote class="gmail_quote" style="margin:0px 0px 0px
0.8ex;border-left:1px solid
rgb(204,204,204);padding-left:1ex">
Best regards,<br class="">
Marcel<br class="">
<br class="">
<br class="">
------------------------------------------------------------------------------------------------<br class="">
------------------------------------------------------------------------------------------------<br class="">
Forschungszentrum Juelich GmbH<br class="">
52425 Juelich<br class="">
Sitz der Gesellschaft: Juelich<br class="">
Eingetragen im Handelsregister des Amtsgerichts Dueren Nr.
HR B 3498<br class="">
Vorsitzender des Aufsichtsrats: MinDir Volker Rieke<br class="">
Geschaeftsfuehrung: Prof. Dr.-Ing. Wolfgang Marquardt
(Vorsitzender),<br class="">
Karsten Beneke (stellv. Vorsitzender), Prof. Dr.-Ing. Harald
Bolt<br class="">
------------------------------------------------------------------------------------------------<br class="">
------------------------------------------------------------------------------------------------<br class="">
<br class="">
</blockquote>
</div>
<br clear="all" class="">
<div class=""><br class="">
</div>
-- <br class="">
<div dir="ltr" class="gmail_signature">
<div dir="ltr" class="">
<div class="">
<div dir="ltr" class="">
<div class="">
<div dir="ltr" class="">
<div class="">What most experimenters take for granted before
they begin their experiments is infinitely more
interesting than any results to which their
experiments lead.<br class="">
-- Norbert Wiener</div>
<div class=""><br class="">
</div>
<div class=""><a href="http://www.cse.buffalo.edu/~knepley/" target="_blank" moz-do-not-send="true" class="">https://www.cse.buffalo.edu/~knepley/</a><br class="">
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</blockquote>
<br class="">
</div>
</div></blockquote></div><br class=""></div></div></body></html>