search

ralna / spral

Sparse Parallel Robust Algorithms Library
https://ralna.github.io/spral/
Other
106 stars 26 forks source link

maxfront info seems inconsistent #110

Closed mjacobse closed 1 year ago

mjacobse commented 1 year ago

In the CPU factorization, maxfront seems to be computed differently than in the GPU factorization and the symbolic analysis.

Basically, the CPU factorization takes the maximum of nrow == blkm while the GPU factorization and the symbolic analysis take the maximum of ncol == blkn. And I believe nrow >= ncol by definition.

I am not quite sure which of these is the actual "maximum front size" meant in the documentation. From what I understand, a frontal matrix collects the nonzero elements of the arrowhead for a pivot in its first row/column, which would give a matrix of dimension blkm*blkm, so maxfront would be the maximum of blkm. The maximum of blkn to me would be better described by something like maxsupernode or maxnodesize. However, HSL_MA97 computes maxfront as the maximum of blkn. And indeed, if I change the SSIDS CPU code to use the maximum of ncol, I can get the same results for maxfront as with HSL_MA97. So presumably I am wrong. But in any case, the current mixture of nrow and ncol seems very strange to me.

If someone can tell which variant is the intended one, I'd be happy to propose a change.

jfowkes commented 1 year ago

Good question, @nimgould how is the max front size in a multifrontal method usually defined?

nimgould commented 1 year ago

I can only guess what was intended - I would have thought that the front is the current (assumed dense for efficiency) merge of all matrices involving the current potential pivot - but really you should ask Jennifer Scott as she is a co-author of this work, and the true expert

jfowkes commented 1 year ago

Thanks Nick, I will check with Jennifer on Thursday.

jfowkes commented 1 year ago

Jennifer Scott says

The terminology in these methods is definitely not transparent. The multifrontal code that I actually did all the coding for is hsl_ma77 and, looking again at that, it clearly allocates a square frontal matrix and its size is very clear to see. However, things are less obvious in hsl_MA97 (and SSIDS). ma97 implements a supernodal multifrontal method and, looking at the source code, it does not allocate a frontal matrix in the way that ma77 does but goes directly to storage for a supernode within L. At the moment, I am wondering why blkn is used. I am inclined to think it should be blkm (as in SSIDS CPU version). maxfront is a statistic that is returned to the user ... it is not something that is used for allocating memory in the code so it is possible that the wrong statistic is being returned.

One possibility is to run ma97 and ma57 (and ma77?) on some positive definite examples and see what maxfront is reported.

We will run some tests and check what maxfront is reported by the various multifrontal HSL codes.

jfowkes commented 1 year ago

@mjacobse we are making the following change to HSL_MA97:

Version 2.8.0
Update code and documentation:
   * info%maxfront statistic corrected (it holds the max front size, which is equal to
     the max number of rows in a supernode)
   * info%maxsupernode added to hold what was previously in info%maxfront, which is
     the max number of columns in a supernode

Would you be able to create a PR that fixes maxfront for the SSIDS GPU code and also adds the maxsupernode statistics so that this is consistent with the above?

mjacobse commented 1 year ago

Great, thanks. Sure, see above.