# CombinatorialMultigrid.jl

This package implements the Combinatorial Multigrid Preconditioner *[1]*. The code handles input matrices that are symmetric diagonally dominant with negative off-diagonal entries, a class of matrices that includes graph Laplacians. This work has been supported by NSF grant CCF-#1149048.

In order to install the package simply do the following:

```
Pkg.add("CombinatorialMultigrid")
using CombinatorialMultigrid
```

We present a quick example. Lets load a fairly large example matrix `X`

from the `example`

directory and build the `b`

side. `X`

is an adjacency matrix. `LX`

is the corresponding Laplacian matrix.

```
## load example matrix
file = matopen("../example/X.mat"); X = read(file, "X"); close(file)
LX = lap(X);
b = rand(Float64, size(X, 1));
b = b .- sum(b)/length(b);
```

CMG outputs a preconditioner function that can be used to solve a linear system in the input system. This is done here:

```
t = @elapsed (pfunc, h) = cmg_preconditioner_lap(LX);
@info "Time Required to build CMG Solver: $(t) seconds"
t = @elapsed x = pfunc(b);
@info "Runtime of preconditioner: $(t) seconds"
```

The second output `h`

is a hierarchy of graphs that is implicitly used in `pfunc`

and it is exposed for its potential in other applications. Alternatively, one can bypass the computation of the Laplacian matrix as follows:

```
(pfunc, h) = cmg_preconditioner_adj(X);
```

The above script generates the following output:

```
[ Info: Time Required to build CMG Solver: 3.258120718 seconds
[ Info: Runtime of preconditioner: 0.194163587 seconds
```

We now solve a linear system using CMG. For this purpose we leverage `pcg`

from the `Laplacians`

package. We run the following script:

```
f = pcgSolver(LX,pfunc);
t = @elapsed x = f(b, maxits=40, tol=1e-6,verbose=true);
@info "Time Required to solve system: $(t) seconds"
```

This generates the following output:

```
PCG stopped after: 7.828 seconds and 29 iterations with relative error 8.429320186485909e-7.
[ Info: Time Required to solve system: 8.034237971 seconds
```

For comparison we run `approxchol_lap`

which is the fastest solver from the `Laplacians`

package. We run the following script:

```
solver = approxchol_lap(X; tol=1e-6, maxits=1000, maxtime=Inf, verbose=true, pcgIts=Int[], params=ApproxCholParams());
@info "Time Required to build Lap Solver: $(t) seconds"
t = @elapsed x = solver(b);
@info "Time Required to find x: $(t) seconds"
```

This generates the following output:

```
Using greedy degree ordering. Factorization time: 25.985280990600586
Ratio of operator edges to original edges: 4.548086602013639
ratio of max to min diagonal of laplacian : 583453.0510646806
Solver build time: 26.293 seconds.
[ Info: Time Required to build Lap Solver: 26.304803977 seconds
PCG stopped after: 10.288 seconds and 26 iterations with relative error 9.697886904926194e-7.
[ Info: Time Required to find x: 12.226966502 seconds
```

`CMG`

builds the preconditioner in `3.26 seconds`

compared to `26.31 seconds`

with `approxchol_lap`

. Solving the system takes `7.8 seconds`

with `cmg`

and `10.29 seconds`

with `approxchol_lap`

.

**Citations:**

[1] Ioannis Koutis, Gary L. Miller, David Tolliver, Combinatorial preconditioners and multilevel solvers for problems in computer vision and image processing, Computer Vision and Image Understanding, Volume 115, Issue 12, 2011, Pages 1638-1646, ISSN 1077-3142, https://doi.org/10.1016/j.cviu.2011.05.013.*