[petsc-users] MatOrdering for rectangular matrix

[Barry Smith]

   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 <m.huysegoms at fz-juelich.de> 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 <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/62abefb0/attachment.html>