Template Class Lamg¶

Inheritance Relationships¶

Class Documentation¶

template<class Matrix>
class Lamg : public NetworKit::LinearSolver<Matrix>¶

Represents the interface to the Lean Algebraic Multigrid (LAMG) graph Laplacian linear solver by Oren E. Livne and Achi Brandt.

See also

Livne, Oren E., and Achi Brandt. “Lean algebraic multigrid (LAMG): Fast graph Laplacian

linear solver.” SIAM Journal on Scientific Computing 34.4 (2012): B499-B522.

Public Functions

inline Lamg(const double tolerance = 1e-6)¶

Construct a solver with the given tolerance. The relative residual ||Ax-b||/||b|| will be less than or equal to tolerance after the solver finished.

Parameters:

tolerance –

~Lamg() override = default¶

Default destructor

virtual void setup(const Matrix &laplacianMatrix) override¶

Compute the multigrid hierarchy for the given Laplacian matrix laplacianMatrix.

Note

This method also works for disconnected graphs. If you know that the graph is connected, it is faster to use setupConnected instead.

Parameters:

laplacianMatrix –

virtual void setup(const Graph &graph) override¶

Compute the multigrid hierarchy for the Laplacian matrix that corresponds to the graph G.

Parameters:

• laplacianMatrix –

• G – Graph that corresponds to the laplacianMatrix

void setup(const Matrix &laplacianMatrix, const Graph &G)¶

Compute the multigrid hierarchy for the given Laplacian matrix laplacianMatrix that corresponds to the graph G.

Note

This setup method allows you to skip some computation required for setting up LAMG. You can provide your matrix and graph, which are required for setting up LAMG, via this method to prevent duplicate computation. Note that the output is undefined if the two parameters do not correspond the the same graph.

Parameters:

• laplacianMatrix –

• G – Graph that corresponds to the laplacianMatrix

void setup(const Graph &G, const ComponentDecomposition &decomp)¶

Compute the multigrid hierarchy for the Laplacian matrix that corresponds to the graph G using the existing component decomposition decomp.

Note

This setup method allows you to skip some computation required for setting up LAMG. You can provide your graph and decomposition, which are required for setting up LAMG, via this method to prevent duplicate computation. Note that the output is undefined if the two parameters do not correspond the the same graph.

Parameters:

• G – Graph that corresponds to the laplacianMatrix

• decomp – ComponentDecomposition for the graph G

void setup(const Matrix &laplacianMatrix, const Graph &G, const ComponentDecomposition &decomp)¶

Compute the multigrid hierarchy for the given Laplacian matrix laplacianMatrix that corresponds to the graph G using the existing component decomposition decomp.

Note

This setup method allows you to skip some computation required for setting up LAMG. You can provide your graph and decomposition, which are required for setting up LAMG, via this method to prevent duplicate computation. Note that the output is undefined if the three parameters do not correspond the the same graph.

Parameters:

• laplacianMatrix –

• G – Graph that corresponds to the laplacianMatrix

• decomp – ComponentDecomposition for the graph G

virtual void setupConnected(const Matrix &laplacianMatrix) override¶

Compute the multigrid hierarchy for the given Laplacian matrix laplacianMatrix.

Note

The graph has to be connected for this method to work. Otherwise the output is undefined.

Parameters:

laplacianMatrix –

virtual SolverStatus solve(const Vector &rhs, Vector &result, count maxConvergenceTime = 5 * 60 * 1000, count maxIterations = std::numeric_limits<count>::max()) const override¶

Computes the result for the matrix currently setup and the right-hand side rhs. The maximum spent time can be specified by maxConvergenceTime and the maximum number of iterations can be set by maxIterations.

Parameters:

• rhs –

• result –

• maxConvergenceTime –

• maxIterations –

Returns:

A SolverStatus object which provides some statistics like the final absolute residual.

virtual std::vector<SolverStatus> parallelSolve(const std::vector<Vector> &rhs, std::vector<Vector> &results, count maxConvergenceTime = 5 * 60 * 1000, count maxIterations = std::numeric_limits<count>::max()) const override¶

Compute the results for the matrix currently setup and the right-hand sides rhs. The maximum spent time for each system can be specified by maxConvergenceTime and the maximum number of iterations can be set by maxIterations.

Parameters:

• rhs –

• results –

• maxConvergenceTime –

• maxIterations –

template<typename RHSLoader, typename ResultProcessor>
inline void parallelSolve(const RHSLoader &rhsLoader, const ResultProcessor &resultProcessor, std::pair<count, count> rhsSize, count maxConvergenceTime = 5 * 60 * 1000, count maxIterations = std::numeric_limits<count>::max()) const¶

Abstract parallel solve function that computes and processes results using resultProcessor for the matrix currently setup and the right-hand sides (size of rhsSize) provided by rhsLoader. The maximum spent time for each system can be specified by maxConvergenceTime and the maximum number of iterations can be set by maxIterations.

Note

If the solver does not support parallelism during solves, this function falls back to solving the systems sequentially.

Note

The rhsLoader and resultProcessor are called from multiple threads in parallel.

Parameters:

• rhsLoader –

• resultProcessor –

• rhsSize –

• maxConvergenceTime –

• maxIterations –