Problems reordering a matrix

Hello, I'm trying to use Metis 5 ordering for MUMPS since the 32 bit integers used to allocate memory in Metis 4 were insufficient for some matrices I need to invert. However, it seems Metis 5 gets stuck in an infinite loop somewhere. Here is the output of a debug session with OPTIONS_METIS(METIS_OPTION_DBGLVL) = 1+4+8+16+32+64+128+256. Of course, Metis 4 reorders the matrix without problems.

Any ideas would be appreciated.

Runtime parameters:
Objective type: METIS_OBJTYPE_NODE
Coarsening type: METIS_CTYPE_SHEM
Initial partitioning type: METIS_IPTYPE_EDGE
Refinement type: METIS_RTYPE_SEP1SIDED
Number of balancing constraints: 1
Number of refinement iterations: 10
Random number seed: -1
Number of separators: 1
Compress graph prior to ordering: Yes
Detect & order connected components separately: No
Prunning factor for high degree vertices: 0.000000
Allowed maximum load imbalance: 1.200

Compression: reduction in # of vertices: 514466.
569086 20745962 20745962 [18969] [ -7967:-100763326 ]
569086 20745962 20745962 [18969] [ -7967:-100763326 ]
569086 20745962 20745962 [100] [ -1511449:-100763326 ]
569086 20745962 20745962 [100] [ -1511449:-100763326 ]

Initial Sep: 0
Partitions: [ 0 -100763326] Nv-Nb[569086 0]. ISep: 0 [B]
Balanced sep: 0 at 0, PWGTS: [ 0 -100763326], NBND: 0
Partitions-N1: [ 0 -100763326] Nv-Nb[569086 0]. ISep: 0
Minimum sep: 0 at -1, PWGTS: [ 0 -100763326], NBND: 0
Minimum sep: 0 at -1, PWGTS: [ 0 -100763326], NBND: 0
Partitions: [ 0 -100763326] Nv-Nb[569086 0]. ISep: 0 [B]
Balanced sep: 0 at 0, PWGTS: [ 0 -100763326], NBND: 0
Partitions-N1: [ 0 -100763326] Nv-Nb[569086 0]. ISep: 0
Minimum sep: 0 at -1, PWGTS: [ 0 -100763326], NBND: 0
Minimum sep: 0 at -1, PWGTS: [ 0 -100763326], NBND: 0
Nvtxs: 569086, [ 0 -100763326 0]

569086 20745962 20745962 [18969] [ -7967:-100763326 ]
569086 20745962 20745962 [18969] [ -7967:-100763326 ]
569086 20745962 20745962 [100] [ -1511449:-100763326 ]
569086 20745962 20745962 [100] [ -1511449:-100763326 ]

Nvtxs: 569086, [ 0 -100763326 0]
569086 20745962 20745962 [18969] [ -7967:-100763326 ]
569086 20745962 20745962 [18969] [ -7967:-100763326 ]
569086 20745962 20745962 [100] [ -1511449:-100763326 ]
569086 20745962 20745962 [100] [ -1511449:-100763326 ]

... (ad infinitum)

Submitted by gendou on Fri, 2012-02-03 08:14

RE: Can you create an input file

Can you create an input file for ndmetis and put it somewhere where I can download it to see what is going on with it?

Submitted by karypis on Sun, 2012-02-05 16:19.

RE: As per your request for a

As per your request for a graph that causes ndmetis to hang: http://db.tt/k8rf3Rrs
On my machine, I get:

$ ndmetis bad.graph -iptype edge -dbglvl 509

******************************************************************************
METIS 5.0 Copyright 1998-11, Regents of the University of Minnesota
(HEAD: , Built on: Feb 20 2012, 14:25:42)
size of idx_t: 32bits, real_t: 32bits, idx_t *: 64bits

Graph Information -----------------------------------------------------------
Name: bad.graph, #Vertices: 400, #Edges: 760

Options ---------------------------------------------------------------------
ctype=shem, rtype=1sided, iptype=edge, seed=-1, dbglvl=509
ufactor=1.200, pfactor=0.00, ccorder=NO, compress=YES, , nooutput=NO
niter=10, nseps=1

Node-based Nested Dissection ------------------------------------------------
Runtime parameters:
Objective type: METIS_OBJTYPE_NODE
Coarsening type: METIS_CTYPE_SHEM
Initial partitioning type: METIS_IPTYPE_EDGE
Refinement type: METIS_RTYPE_SEP1SIDED
Number of balancing constraints: 1
Number of refinement iterations: 10
Random number seed: -1
Number of separators: 1
Compress graph prior to ordering: Yes
Detect & order connected components separately: No
Prunning factor for high degree vertices: 0.000000
Allowed maximum load imbalance: 1.200

Compression: reduction in # of vertices: 0.
400 1520 1520 [50] [ 0: 0 ]
400 1520 1520 [50] [ 0: 0 ]
Initial Sep: 0
Partitions: [ 0 0] Nv-Nb[ 400 9]. ISep: 0 [B]
Moved 301 to 1, Gain: 0, [ 0 0 0]
Moved 98 to 1, Gain: 0, [ 0 0 0]
Moved 99 to 1, Gain: 0, [ 0 0 0]
Moved 97 to 1, Gain: 0, [ 0 0 0]
Moved 280 to 1, Gain: 0, [ 0 0 0]
Moved 300 to 1, Gain: 0, [ 0 0 0]
Moved 78 to 1, Gain: 0, [ 0 0 0]
Moved 118 to 1, Gain: 0, [ 0 0 0]
Moved 320 to 1, Gain: 0, [ 0 0 0]
Balanced sep: 0 at 9, PWGTS: [ 0 0], NBND: 0
Partitions-N1: [ 0 0] Nv-Nb[ 400 0]. ISep: 0
Minimum sep: 0 at -1, PWGTS: [ 0 0], NBND: 0
Minimum sep: 0 at -1, PWGTS: [ 0 0], NBND: 0
Nvtxs: 400, [ 0 0 0]
400 1520 1520 [50] [ 0: 0 ]
400 1520 1520 [50] [ 0: 0 ]

(which continues endlessly) If you s/^ 0/ 1/ (change all the vertex weights to 1), it returns a reordering immediately.

Submitted by jfettig on Mon, 2012-02-20 21:57.

RE: It seems the problem is that

It seems the problem is that MUMPS is passing a vertex weight array to METIS that is all zero. This results in endless recursion. If you pass in a vertex weight array that is all ones, METIS returns successfully. Also, if you run in a debugger and catch the call to METIS, then set vwgt=0x0, it runs fine. So I think the issue is that previously METIS handled all-zero vertex weights and now it doesn't.

Submitted by jfettig on Mon, 2012-02-20 21:47.

RE: Not all zero

Thanks for looking into the issue. Just to check, I wrote the weight array to disk (FILS in src/dmumps_part2.F) from MUMPS and found that it did not contain zero values, but only values in the range 29181 - 42191. I also tried setting the values to 1 artificially but that did not help.

Submitted by gendou on Tue, 2012-02-21 08:45.

Navigation Menu

Problems reordering a matrix

RE: Can you create an input file

RE: As per your request for a

RE: It seems the problem is that

RE: Not all zero