Linear Solver Benchmark

This library is a benchmark for implementations of sparse cholesky factorization methods.

Table of Contents

• Linear Solver Benchmark
  • Table of Contents
  • Solvers
  • Compilation
  • Adding New Test Data
  • Running The Benchmark
  • Generating Interactive Altair Plot
  • Benchmark Structure
  • Additional Reference Documentation
  • Contributing
  • Licensing

Solvers

The following solvers are benchmarked:

• Eigen::SimplicialLDLT
• Eigen::CholmodSupernodalLLT
• Eigen::CholmodSimplicialLLT
• Eigen::AccelerateLLT Apple Silicon only
• Eigen::AccelerateLDLT Apple Silicon only
• Sympiler Apple only
• Eigen::PardisoLLT Windows only

All solvers are accessed using the Polysolve wrapper library.

Compilation

All compile dependencies are handled by CMake, so the following should work on any platform:

cd <repo>
mkdir build
cd build
cmake ..
cmake --build . -j 8

Before the benchmark can be ran, there must be linear systems to benchmark on in the /data directory. These systems are stored in a compressed json .zst format.

Adding New Test Data

To save matrices in the correct format, perform the following:

1. Download the save_problem.h header file, and add it to your application. It only depends on Eigen and the STL.

2. Save the linear system within your application

   #include "save_problem.h"
   
   // Fill matrices for linear system A*x = b
   Eigen::SparseMatrix<double> A;
   Eigen::MatrixXd b;
   
   // A = ...
   // b = ...
   
   // Describe metadata about the problem
   benchy::io::Problem<double> problem;
   problem.A = A;
   problem.b = b;
   problem.is_symmetric_positive_definite = 1;
   problem.is_sequence_of_problems = 0;
   problem.dimension = 3;
   problem.description = "Linear elasticity simulation in 3D";
   problem.project_url = "https://github.com/polyfem/polyfem/";
   problem.contact_email = "my.name@gmail.com";
   
   // Save the problem to a json file
   benchy::io::save_problem("my_problem.json", problem);

   If you have multiple rhs, save them as multiple columns of a single rhs matrix b.mtx.

3. Compile and run our utility to convert and compress the data

   <build>/tools/benchy_convert my_problem.json my_problem.zst
   

   Tip: For faster compilation, compile the tool only with cmake -DBENCHY_TOOLS=ON -DBENCHY_TESTS=OFF ...

4. Copy the compressed linear system to the corresponding problem folder in data/.

   cp my_problem.zst <repo>/data/my_project
   

Running The Benchmark

To run the benchmark, first ensure there are systems in the execute

./build/tools/benchmark_cli

The benchmark command-line interface exposes three parameters:

1. --input A directory to the dataset to be benchmarked on. Defaults to ./data. See Adding New Test Data
2. --regex The paths of all .zst files in the input directory are collected and then filtered using the regex. For example, to access only the systems in the harmonic subdirectory, use ./build/tools/benchmark_cli --regex '.*/harmonic/.*'. Defaults to .*.zst
3. --output Directory to output the benchmark csv data to. Defaults to ./output.

Depending on the number of systems and solvers, the benchmark could take a long time to run.

Generating Interactive Altair Plot

Benchy comes with an interactive plot, written with Altair, that can be used to explore the results of the benchmark.

After running, the benchmark should output a file, output/<date>_<time>_benchmark_data.csv. To generate the interactive plot, execute the following from the solver-benchmark directory:

conda env create -f scripts/benchy-analysis.yml
conda activate benchy-analysis
python scripts/analysis.py --input ./path/to/benchmark_data.csv

This should output a file polars-composite.html which can be viewed in a browser.

Benchmark Structure

For each solver listed above, the benchmark times the following:

• Analyze phase: symbolic factorization of $A$
• Factorize phase: finding $L$ such that $A = LL^T$
• Solve phase: Solving $Ax = b$ using the factorization

The rough structure of the benchmark is as follows:

for (Each System in Systems)
{
    for (Each Solver)
    {
        for (Each Phase : [Analyze, Factorize, Solve])
        {
            time Solver Phase for System
        }
    }
}

The main dependency of the project is Celero. Celero provides the ability to consistently time pieces of code. Celero actually runs each benchmark multiple times to gather reliable data. See Celero Program Flow for more details.

Additional Reference Documentation

To contribute a solver to the benchmark, a Polysolve::LinearSolver wrapper subclass must be written. See the reference documentation for more details on the internals of the benchmark. To build documentation, complete the following:

1. Configure cmake with the BENCHY_DOCS on, by e.g

mkdir build
cd build
cmake -DBENCHY_DOCS=ON ..

2. Build the documentation

cmake --build . --target doc -j8

3. View the index.html file

firefox html/index.html

Contributing

Contributions are welcomed! Read the Contributing Guide for more information.

Licensing

This project is licensed under the Apache 2.0 License. See LICENSE for more information.