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