Multigrid implementation status

[lahwaacz]

I noticed there is an implementation of algebraic multigrid based on AmgX. It is not mentioned in your papers so it is probably more recent. Is it considered complete or still work in progress? Do you plan to implement more smoothers or coarsening methods (like "classical" or smoothed aggregation)?

I'm asking because I tried using Ginkgo's AMG in my PDE solver and it performed very poorly. I can reproduce the problem on a simple Poisson equation in 2D (5-point stencil) and 3D (7-point stencil) which can be compared with Hypre:

• my Ginkgo solvers: 2D, 3D
• the multigrid config is based on the multigrid-preconditioned-solver example
• my Hypre solvers: 2D, 3D

The actual results (iterations of AMG-preconditioned conjugate gradients):

2D grid size (^2)	Ginkgo (Jacobi)	Ginkgo (AmgX)	Hypre (BoomerAMG)
16	19	10	5
32	50	14	5
64	100	20	5
128	192	45	6
256	381	101	6
512	755	181	6
1024	1494	318	6

3D grid size (^3)	Ginkgo (Jacobi)	Ginkgo (AmgX)	Hypre (BoomerAMG)
16	40	9	5
32	92	16	5
64	181	28	6
128	350	53	6
256	684	93	7

On the 1024x1024 grid, Ginkgo-Jacobi needed about 25 seconds to solve the system, but Ginkgo-AmgX needed about 72 seconds and Hypre needed just about 2 seconds (which includes even time to convert the matrix to the Hypre data structure). On the 256^3 grid it's 201 sec vs 490 sec vs 53 sec. (benchmarked on Intel(R) Xeon(R) CPU E5-2630 v3 @ 2.40GHz using 8 OpenMP threads)

Obviously the problem seems to be that this AmgX configuration does not provide (nearly) grid independent convergence rate, but stays similar to Jacobi (the iterations count with AmgX is almost double on the next grid).

Also note that Hypre can be configured to show info about the multigrid hierarchy, which is very useful for performance tuning. It would be nice if Ginkgo could do something similar:

BoomerAMG SETUP PARAMETERS:

 Max levels = 25
 Num levels = 8

 Strength Threshold = 0.250000
 Interpolation Truncation Factor = 0.000000
 Maximum Row Sum Threshold for Dependency Weakening = 0.900000

 Coarsening Type = Falgout-CLJP
 measures are determined locally


 No global partition option chosen.

 Interpolation = modified classical interpolation

Operator Matrix Information:

             nonzero            entries/row          row sums
lev    rows  entries sparse   min  max     avg      min         max
======================================================================
  0   16384    81408  0.000     3    5     5.0   0.000e+00   2.000e+00
  1    8192    72706  0.001     4    9     8.9   0.000e+00   2.500e+00
  2    2110    18730  0.004     4   12     8.9   0.000e+00   3.020e+00
  3     544     4772  0.016     5   11     8.8  -1.110e-16   2.660e+00
  4     138     1200  0.063     5   13     8.7  -9.368e-16   2.987e+00
  5      36      328  0.253     4   15     9.1  -1.031e-15   2.570e+00
  6      11       87  0.719     5   10     7.9   1.014e+00   2.554e+00
  7       3        9  1.000     3    3     3.0   2.504e+00   2.859e+00


Interpolation Matrix Information:
                    entries/row        min        max            row sums
lev  rows x cols  min  max  avgW     weight      weight       min         max
================================================================================
  0 16384 x 8192    1    4   4.0   2.500e-01   2.500e-01   5.000e-01   1.000e+00
  1  8192 x 2110    1    4   2.7   7.692e-02   5.000e-01   2.857e-01   1.000e+00
  2  2110 x 544     1    4   2.6   6.950e-02   5.503e-01   1.110e-01   1.000e+00
  3   544 x 138     1    4   2.5   7.307e-02   5.388e-01   1.243e-01   1.000e+00
  4   138 x 36      0    4   2.2   6.429e-02   5.240e-01   0.000e+00   1.000e+00
  5    36 x 11      0    4   2.2   2.370e-02   5.171e-01   0.000e+00   1.000e+00
  6    11 x 3       1    3   1.4   6.097e-02   4.653e-01   9.966e-02   1.000e+00


     Complexity:    grid = 1.673462
                operator = 2.201749
                memory = 3.003132




BoomerAMG SOLVER PARAMETERS:

  Maximum number of cycles:         1
  Stopping Tolerance:               0.000000e+00
  Cycle type (1 = V, 2 = W, etc.):  1

  Relaxation Parameters:
   Visiting Grid:                     down   up  coarse
            Number of sweeps:            1    1     1
   Type 0=Jac, 3=hGS, 6=hSGS, 9=GE:      6    6     9
   Point types, partial sweeps (1=C, -1=F):
                  Pre-CG relaxation (down):   1  -1
                   Post-CG relaxation (up):  -1   1
                             Coarsest grid:   0

[yhmtsai]

The multigrid will be presented in PPAM2022.
The current multigrid is not the final version or the paper version yet.
The result is not out of my expectation.
AmgX with aggregation size 2 takes the strongest neighbor. We choose the neighbor with the largest column index if some neighbors share the same weight. It leads to series indication (e1->e2->e3->...->en) such that each iteration only matches few pairs in the stencil problem. Thus, the dimension reduction is slow when generating the coarse level (i.e. each linear system has almost the same size as the original case such that the performance is quite slow.

[lahwaacz]

The result is not out of my expectation.

So you expect AmgX to be more than twice slower than the basic Jacobi preconditioner? Otherwise, if only the numbers of iterations are within your expectation, then there are still performance problems somewhere in the implementation to fix...

AmgX with aggregation size 2 takes the strongest neighbor.

What's this aggregation size parameter? Is it configurable in Ginkgo?

Also: have you considered different coarsening strategies than aggregation? E.g. the "classical" AMG, which is also implemented in AmgX.

[yhmtsai]

no, I only means the bad performance of AMG with PGM makes sense currently because it almost solves max_level linear system with the same size of original system. That means we do not get benefit from the coarsening.
For the stencil problem on PGM, we can add little random weight on the weight matrix or use other concepts to make more matches such that PGM works better than the current one.
About the aggregation size or different coarsening methods, Ginkgo currently does not provide them, but we are implementing them.

[lahwaacz]

Ok, thanks for the clarification and good luck with your work!