spbenchsolver.h

Go to the documentation of this file.

// This file is part of Eigen, a lightweight C++ template library
// for linear algebra.
//
// Copyright (C) 2012 Désiré Nuentsa-Wakam <desire.nuentsa_wakam@inria.fr>
//
// This Source Code Form is subject to the terms of the Mozilla
// Public License v. 2.0. If a copy of the MPL was not distributed
// with this file, You can obtain one at http://mozilla.org/MPL/2.0/.
 
#include <iostream>
#include <fstream>
#include <Eigen/SparseCore>
#include <bench/BenchTimer.h>
#include <cstdlib>
#include <string>
#include <Eigen/Cholesky>
#include <Eigen/Jacobi>
#include <Eigen/Householder>
#include <Eigen/IterativeLinearSolvers>
#include <unsupported/Eigen/IterativeSolvers>
#include <Eigen/LU>
#include <unsupported/Eigen/SparseExtra>
#include <Eigen/SparseLU>
 
#include "spbenchstyle.h"
 
#ifdef EIGEN_METIS_SUPPORT
#include <Eigen/MetisSupport>
#endif
 
#ifdef EIGEN_CHOLMOD_SUPPORT
#include <Eigen/CholmodSupport>
#endif
 
#ifdef EIGEN_UMFPACK_SUPPORT
#include <Eigen/UmfPackSupport>
#endif
 
#ifdef EIGEN_KLU_SUPPORT
#include <Eigen/KLUSupport>
#endif
 
#ifdef EIGEN_PARDISO_SUPPORT
#include <Eigen/PardisoSupport>
#endif
 
#ifdef EIGEN_SUPERLU_SUPPORT
#include <Eigen/SuperLUSupport>
#endif
 
#ifdef EIGEN_PASTIX_SUPPORT
#include <Eigen/PaStiXSupport>
#endif
 
// CONSTANTS
#define EIGEN_UMFPACK 10
#define EIGEN_KLU 11
#define EIGEN_SUPERLU 20
#define EIGEN_PASTIX 30
#define EIGEN_PARDISO 40
#define EIGEN_SPARSELU_COLAMD 50
#define EIGEN_SPARSELU_METIS 51
#define EIGEN_BICGSTAB 60
#define EIGEN_BICGSTAB_ILUT 61
#define EIGEN_GMRES 70
#define EIGEN_GMRES_ILUT 71
#define EIGEN_SIMPLICIAL_LDLT 80
#define EIGEN_CHOLMOD_LDLT 90
#define EIGEN_PASTIX_LDLT 100
#define EIGEN_PARDISO_LDLT 110
#define EIGEN_SIMPLICIAL_LLT 120
#define EIGEN_CHOLMOD_SUPERNODAL_LLT 130
#define EIGEN_CHOLMOD_SIMPLICIAL_LLT 140
#define EIGEN_PASTIX_LLT 150
#define EIGEN_PARDISO_LLT 160
#define EIGEN_CG 170
#define EIGEN_CG_PRECOND 180
 
using namespace Eigen;
using namespace std;
 
// Global variables for input parameters
int MaximumIters;      // Maximum number of iterations
double RelErr;         // Relative error of the computed solution
double best_time_val;  // Current best time overall solvers
int best_time_id;      //  id of the best solver for the current system
 
template <typename T>
inline typename NumTraits<T>::Real test_precision() {
  return NumTraits<T>::dummy_precision();
}
template <>
inline float test_precision<float>() {
  return 1e-3f;
}
template <>
inline double test_precision<double>() {
  return 1e-6;
}
template <>
inline float test_precision<std::complex<float> >() {
  return test_precision<float>();
}
template <>
inline double test_precision<std::complex<double> >() {
  return test_precision<double>();
}
 
void printStatheader(std::ofstream& out) {
  // Print XML header
  // NOTE It would have been much easier to write these XML documents using external libraries like tinyXML or
  // Xerces-C++.
 
  out << "<?xml version='1.0' encoding='UTF-8'?> \n";
  out << "<?xml-stylesheet type='text/xsl' href='#stylesheet' ?> \n";
  out << "<!DOCTYPE BENCH  [\n<!ATTLIST xsl:stylesheet\n id\t ID  #REQUIRED>\n]>";
  out << "\n\n<!-- Generated by the Eigen library -->\n";
 
  out << "\n<BENCH> \n";  // root XML element
  // Print the xsl style section
  printBenchStyle(out);
  // List all available solvers
  out << " <AVAILSOLVER> \n";
#ifdef EIGEN_UMFPACK_SUPPORT
  out << "  <SOLVER ID='" << EIGEN_UMFPACK << "'>\n";
  out << "   <TYPE> LU </TYPE> \n";
  out << "   <PACKAGE> UMFPACK </PACKAGE> \n";
  out << "  </SOLVER> \n";
#endif
#ifdef EIGEN_KLU_SUPPORT
  out << "  <SOLVER ID='" << EIGEN_KLU << "'>\n";
  out << "   <TYPE> LU </TYPE> \n";
  out << "   <PACKAGE> KLU </PACKAGE> \n";
  out << "  </SOLVER> \n";
#endif
#ifdef EIGEN_SUPERLU_SUPPORT
  out << "  <SOLVER ID='" << EIGEN_SUPERLU << "'>\n";
  out << "   <TYPE> LU </TYPE> \n";
  out << "   <PACKAGE> SUPERLU </PACKAGE> \n";
  out << "  </SOLVER> \n";
#endif
#ifdef EIGEN_CHOLMOD_SUPPORT
  out << "  <SOLVER ID='" << EIGEN_CHOLMOD_SIMPLICIAL_LLT << "'>\n";
  out << "   <TYPE> LLT SP</TYPE> \n";
  out << "   <PACKAGE> CHOLMOD </PACKAGE> \n";
  out << "  </SOLVER> \n";
 
  out << "  <SOLVER ID='" << EIGEN_CHOLMOD_SUPERNODAL_LLT << "'>\n";
  out << "   <TYPE> LLT</TYPE> \n";
  out << "   <PACKAGE> CHOLMOD </PACKAGE> \n";
  out << "  </SOLVER> \n";
 
  out << "  <SOLVER ID='" << EIGEN_CHOLMOD_LDLT << "'>\n";
  out << "   <TYPE> LDLT </TYPE> \n";
  out << "   <PACKAGE> CHOLMOD </PACKAGE> \n";
  out << "  </SOLVER> \n";
#endif
#ifdef EIGEN_PARDISO_SUPPORT
  out << "  <SOLVER ID='" << EIGEN_PARDISO << "'>\n";
  out << "   <TYPE> LU </TYPE> \n";
  out << "   <PACKAGE> PARDISO </PACKAGE> \n";
  out << "  </SOLVER> \n";
 
  out << "  <SOLVER ID='" << EIGEN_PARDISO_LLT << "'>\n";
  out << "   <TYPE> LLT </TYPE> \n";
  out << "   <PACKAGE> PARDISO </PACKAGE> \n";
  out << "  </SOLVER> \n";
 
  out << "  <SOLVER ID='" << EIGEN_PARDISO_LDLT << "'>\n";
  out << "   <TYPE> LDLT </TYPE> \n";
  out << "   <PACKAGE> PARDISO </PACKAGE> \n";
  out << "  </SOLVER> \n";
#endif
#ifdef EIGEN_PASTIX_SUPPORT
  out << "  <SOLVER ID='" << EIGEN_PASTIX << "'>\n";
  out << "   <TYPE> LU </TYPE> \n";
  out << "   <PACKAGE> PASTIX </PACKAGE> \n";
  out << "  </SOLVER> \n";
 
  out << "  <SOLVER ID='" << EIGEN_PASTIX_LLT << "'>\n";
  out << "   <TYPE> LLT </TYPE> \n";
  out << "   <PACKAGE> PASTIX </PACKAGE> \n";
  out << "  </SOLVER> \n";
 
  out << "  <SOLVER ID='" << EIGEN_PASTIX_LDLT << "'>\n";
  out << "   <TYPE> LDLT </TYPE> \n";
  out << "   <PACKAGE> PASTIX </PACKAGE> \n";
  out << "  </SOLVER> \n";
#endif
 
  out << "  <SOLVER ID='" << EIGEN_BICGSTAB << "'>\n";
  out << "   <TYPE> BICGSTAB </TYPE> \n";
  out << "   <PACKAGE> EIGEN </PACKAGE> \n";
  out << "  </SOLVER> \n";
 
  out << "  <SOLVER ID='" << EIGEN_BICGSTAB_ILUT << "'>\n";
  out << "   <TYPE> BICGSTAB_ILUT </TYPE> \n";
  out << "   <PACKAGE> EIGEN </PACKAGE> \n";
  out << "  </SOLVER> \n";
 
  out << "  <SOLVER ID='" << EIGEN_GMRES_ILUT << "'>\n";
  out << "   <TYPE> GMRES_ILUT </TYPE> \n";
  out << "   <PACKAGE> EIGEN </PACKAGE> \n";
  out << "  </SOLVER> \n";
 
  out << "  <SOLVER ID='" << EIGEN_SIMPLICIAL_LDLT << "'>\n";
  out << "   <TYPE> LDLT </TYPE> \n";
  out << "   <PACKAGE> EIGEN </PACKAGE> \n";
  out << "  </SOLVER> \n";
 
  out << "  <SOLVER ID='" << EIGEN_SIMPLICIAL_LLT << "'>\n";
  out << "   <TYPE> LLT </TYPE> \n";
  out << "   <PACKAGE> EIGEN </PACKAGE> \n";
  out << "  </SOLVER> \n";
 
  out << "  <SOLVER ID='" << EIGEN_CG << "'>\n";
  out << "   <TYPE> CG </TYPE> \n";
  out << "   <PACKAGE> EIGEN </PACKAGE> \n";
  out << "  </SOLVER> \n";
 
  out << "  <SOLVER ID='" << EIGEN_SPARSELU_COLAMD << "'>\n";
  out << "   <TYPE> LU_COLAMD </TYPE> \n";
  out << "   <PACKAGE> EIGEN </PACKAGE> \n";
  out << "  </SOLVER> \n";
 
#ifdef EIGEN_METIS_SUPPORT
  out << "  <SOLVER ID='" << EIGEN_SPARSELU_METIS << "'>\n";
  out << "   <TYPE> LU_METIS </TYPE> \n";
  out << "   <PACKAGE> EIGEN </PACKAGE> \n";
  out << "  </SOLVER> \n";
#endif
  out << " </AVAILSOLVER> \n";
}
 
template <typename Solver, typename Scalar>
void call_solver(Solver& solver, const int solver_id, const typename Solver::MatrixType& A,
                 const Matrix<Scalar, Dynamic, 1>& b, const Matrix<Scalar, Dynamic, 1>& refX, std::ofstream& statbuf) {
  double total_time;
  double compute_time;
  double solve_time;
  double rel_error;
  Matrix<Scalar, Dynamic, 1> x;
  BenchTimer timer;
  timer.reset();
  timer.start();
  solver.compute(A);
  if (solver.info() != Success) {
    std::cerr << "Solver failed ... \n";
    return;
  }
  timer.stop();
  compute_time = timer.value();
  statbuf << "    <TIME>\n";
  statbuf << "     <COMPUTE> " << timer.value() << "</COMPUTE>\n";
  std::cout << "COMPUTE TIME : " << timer.value() << std::endl;
 
  timer.reset();
  timer.start();
  x = solver.solve(b);
  if (solver.info() == NumericalIssue) {
    std::cerr << "Solver failed ... \n";
    return;
  }
  timer.stop();
  solve_time = timer.value();
  statbuf << "     <SOLVE> " << timer.value() << "</SOLVE>\n";
  std::cout << "SOLVE TIME : " << timer.value() << std::endl;
 
  total_time = solve_time + compute_time;
  statbuf << "     <TOTAL> " << total_time << "</TOTAL>\n";
  std::cout << "TOTAL TIME : " << total_time << std::endl;
  statbuf << "    </TIME>\n";
 
  // Verify the relative error
  if (refX.size() != 0)
    rel_error = (refX - x).norm() / refX.norm();
  else {
    // Compute the relative residual norm
    Matrix<Scalar, Dynamic, 1> temp;
    temp = A * x;
    rel_error = (b - temp).norm() / b.norm();
  }
  statbuf << "    <ERROR> " << rel_error << "</ERROR>\n";
  std::cout << "REL. ERROR : " << rel_error << "\n\n";
  if (rel_error <= RelErr) {
    // check the best time if convergence
    if (!best_time_val || (best_time_val > total_time)) {
      best_time_val = total_time;
      best_time_id = solver_id;
    }
  }
}
 
template <typename Solver, typename Scalar>
void call_directsolver(Solver& solver, const int solver_id, const typename Solver::MatrixType& A,
                       const Matrix<Scalar, Dynamic, 1>& b, const Matrix<Scalar, Dynamic, 1>& refX,
                       std::string& statFile) {
  std::ofstream statbuf(statFile.c_str(), std::ios::app);
  statbuf << "   <SOLVER_STAT ID='" << solver_id << "'>\n";
  call_solver(solver, solver_id, A, b, refX, statbuf);
  statbuf << "   </SOLVER_STAT>\n";
  statbuf.close();
}
 
template <typename Solver, typename Scalar>
void call_itersolver(Solver& solver, const int solver_id, const typename Solver::MatrixType& A,
                     const Matrix<Scalar, Dynamic, 1>& b, const Matrix<Scalar, Dynamic, 1>& refX,
                     std::string& statFile) {
  solver.setTolerance(RelErr);
  solver.setMaxIterations(MaximumIters);
 
  std::ofstream statbuf(statFile.c_str(), std::ios::app);
  statbuf << " <SOLVER_STAT ID='" << solver_id << "'>\n";
  call_solver(solver, solver_id, A, b, refX, statbuf);
  statbuf << "   <ITER> " << solver.iterations() << "</ITER>\n";
  statbuf << " </SOLVER_STAT>\n";
  std::cout << "ITERATIONS : " << solver.iterations() << "\n\n\n";
}
 
template <typename Scalar>
void SelectSolvers(const SparseMatrix<Scalar>& A, unsigned int sym, Matrix<Scalar, Dynamic, 1>& b,
                   const Matrix<Scalar, Dynamic, 1>& refX, std::string& statFile) {
  typedef SparseMatrix<Scalar, ColMajor> SpMat;
  // First, deal with Nonsymmetric and symmetric matrices
  best_time_id = 0;
  best_time_val = 0.0;
// UMFPACK
#ifdef EIGEN_UMFPACK_SUPPORT
  {
    cout << "Solving with UMFPACK LU ... \n";
    UmfPackLU<SpMat> solver;
    call_directsolver(solver, EIGEN_UMFPACK, A, b, refX, statFile);
  }
#endif
// KLU
#ifdef EIGEN_KLU_SUPPORT
  {
    cout << "Solving with KLU LU ... \n";
    KLU<SpMat> solver;
    call_directsolver(solver, EIGEN_KLU, A, b, refX, statFile);
  }
#endif
  // SuperLU
#ifdef EIGEN_SUPERLU_SUPPORT
  {
    cout << "\nSolving with SUPERLU ... \n";
    SuperLU<SpMat> solver;
    call_directsolver(solver, EIGEN_SUPERLU, A, b, refX, statFile);
  }
#endif
 
  // PaStix LU
#ifdef EIGEN_PASTIX_SUPPORT
  {
    cout << "\nSolving with PASTIX LU ... \n";
    PastixLU<SpMat> solver;
    call_directsolver(solver, EIGEN_PASTIX, A, b, refX, statFile);
  }
#endif
 
  // PARDISO LU
#ifdef EIGEN_PARDISO_SUPPORT
  {
    cout << "\nSolving with PARDISO LU ... \n";
    PardisoLU<SpMat> solver;
    call_directsolver(solver, EIGEN_PARDISO, A, b, refX, statFile);
  }
#endif
 
  // Eigen SparseLU METIS
  cout << "\n Solving with Sparse LU AND COLAMD ... \n";
  SparseLU<SpMat, COLAMDOrdering<int> > solver;
  call_directsolver(solver, EIGEN_SPARSELU_COLAMD, A, b, refX, statFile);
// Eigen SparseLU METIS
#ifdef EIGEN_METIS_SUPPORT
  {
    cout << "\n Solving with Sparse LU AND METIS ... \n";
    SparseLU<SpMat, MetisOrdering<int> > solver;
    call_directsolver(solver, EIGEN_SPARSELU_METIS, A, b, refX, statFile);
  }
#endif
 
  // BiCGSTAB
  {
    cout << "\nSolving with BiCGSTAB ... \n";
    BiCGSTAB<SpMat> solver;
    call_itersolver(solver, EIGEN_BICGSTAB, A, b, refX, statFile);
  }
  // BiCGSTAB+ILUT
  {
    cout << "\nSolving with BiCGSTAB and ILUT ... \n";
    BiCGSTAB<SpMat, IncompleteLUT<Scalar> > solver;
    call_itersolver(solver, EIGEN_BICGSTAB_ILUT, A, b, refX, statFile);
  }
 
  // GMRES
  //   {
  //     cout << "\nSolving with GMRES ... \n";
  //     GMRES<SpMat> solver;
  //     call_itersolver(solver, EIGEN_GMRES, A, b, refX,statFile);
  //   }
  // GMRES+ILUT
  {
    cout << "\nSolving with GMRES and ILUT ... \n";
    GMRES<SpMat, IncompleteLUT<Scalar> > solver;
    call_itersolver(solver, EIGEN_GMRES_ILUT, A, b, refX, statFile);
  }
 
  // Hermitian and not necessarily positive-definites
  if (sym != NonSymmetric) {
    // Internal Cholesky
    {
      cout << "\nSolving with Simplicial LDLT ... \n";
      SimplicialLDLT<SpMat, Lower> solver;
      call_directsolver(solver, EIGEN_SIMPLICIAL_LDLT, A, b, refX, statFile);
    }
 
// CHOLMOD
#ifdef EIGEN_CHOLMOD_SUPPORT
    {
      cout << "\nSolving with CHOLMOD LDLT ... \n";
      CholmodDecomposition<SpMat, Lower> solver;
      solver.setMode(CholmodLDLt);
      call_directsolver(solver, EIGEN_CHOLMOD_LDLT, A, b, refX, statFile);
    }
#endif
 
// PASTIX LLT
#ifdef EIGEN_PASTIX_SUPPORT
    {
      cout << "\nSolving with PASTIX LDLT ... \n";
      PastixLDLT<SpMat, Lower> solver;
      call_directsolver(solver, EIGEN_PASTIX_LDLT, A, b, refX, statFile);
    }
#endif
 
// PARDISO LLT
#ifdef EIGEN_PARDISO_SUPPORT
    {
      cout << "\nSolving with PARDISO LDLT ... \n";
      PardisoLDLT<SpMat, Lower> solver;
      call_directsolver(solver, EIGEN_PARDISO_LDLT, A, b, refX, statFile);
    }
#endif
  }
 
  // Now, symmetric POSITIVE DEFINITE matrices
  if (sym == SPD) {
    // Internal Sparse Cholesky
    {
      cout << "\nSolving with SIMPLICIAL LLT ... \n";
      SimplicialLLT<SpMat, Lower> solver;
      call_directsolver(solver, EIGEN_SIMPLICIAL_LLT, A, b, refX, statFile);
    }
 
// CHOLMOD
#ifdef EIGEN_CHOLMOD_SUPPORT
    {
      // CholMOD SuperNodal LLT
      cout << "\nSolving with CHOLMOD LLT (Supernodal)... \n";
      CholmodDecomposition<SpMat, Lower> solver;
      solver.setMode(CholmodSupernodalLLt);
      call_directsolver(solver, EIGEN_CHOLMOD_SUPERNODAL_LLT, A, b, refX, statFile);
      // CholMod Simplicial LLT
      cout << "\nSolving with CHOLMOD LLT (Simplicial) ... \n";
      solver.setMode(CholmodSimplicialLLt);
      call_directsolver(solver, EIGEN_CHOLMOD_SIMPLICIAL_LLT, A, b, refX, statFile);
    }
#endif
 
// PASTIX LLT
#ifdef EIGEN_PASTIX_SUPPORT
    {
      cout << "\nSolving with PASTIX LLT ... \n";
      PastixLLT<SpMat, Lower> solver;
      call_directsolver(solver, EIGEN_PASTIX_LLT, A, b, refX, statFile);
    }
#endif
 
// PARDISO LLT
#ifdef EIGEN_PARDISO_SUPPORT
    {
      cout << "\nSolving with PARDISO LLT ... \n";
      PardisoLLT<SpMat, Lower> solver;
      call_directsolver(solver, EIGEN_PARDISO_LLT, A, b, refX, statFile);
    }
#endif
 
    // Internal CG
    {
      cout << "\nSolving with CG ... \n";
      ConjugateGradient<SpMat, Lower> solver;
      call_itersolver(solver, EIGEN_CG, A, b, refX, statFile);
    }
    // CG+IdentityPreconditioner
    //     {
    //       cout << "\nSolving with CG and IdentityPreconditioner ... \n";
    //       ConjugateGradient<SpMat, Lower, IdentityPreconditioner> solver;
    //       call_itersolver(solver,EIGEN_CG_PRECOND, A, b, refX,statFile);
    //     }
  }  // End SPD matrices
}
 
/* Browse all the matrices available in the specified folder
 * and solve the associated linear system.
 * The results of each solve are printed in the standard output
 * and optionally in the provided html file
 */
template <typename Scalar>
void Browse_Matrices(const string folder, bool statFileExists, std::string& statFile, int maxiters, double tol) {
  MaximumIters = maxiters;  // Maximum number of iterations, global variable
  RelErr = tol;             // Relative residual error  as stopping criterion for iterative solvers
  MatrixMarketIterator<Scalar> it(folder);
  for (; it; ++it) {
    // print the infos for this linear system
    if (statFileExists) {
      std::ofstream statbuf(statFile.c_str(), std::ios::app);
      statbuf << "<LINEARSYSTEM> \n";
      statbuf << "   <MATRIX> \n";
      statbuf << "     <NAME> " << it.matname() << " </NAME>\n";
      statbuf << "     <SIZE> " << it.matrix().rows() << " </SIZE>\n";
      statbuf << "     <ENTRIES> " << it.matrix().nonZeros() << "</ENTRIES>\n";
      if (it.sym() != NonSymmetric) {
        statbuf << "     <SYMMETRY> Symmetric </SYMMETRY>\n";
        if (it.sym() == SPD)
          statbuf << "     <POSDEF> YES </POSDEF>\n";
        else
          statbuf << "     <POSDEF> NO </POSDEF>\n";
 
      } else {
        statbuf << "     <SYMMETRY> NonSymmetric </SYMMETRY>\n";
        statbuf << "     <POSDEF> NO </POSDEF>\n";
      }
      statbuf << "   </MATRIX> \n";
      statbuf.close();
    }
 
    cout << "\n\n===================================================== \n";
    cout << " ======  SOLVING WITH MATRIX " << it.matname() << " ====\n";
    cout << " =================================================== \n\n";
    Matrix<Scalar, Dynamic, 1> refX;
    if (it.hasrefX()) refX = it.refX();
    // Call all suitable solvers for this linear system
    SelectSolvers<Scalar>(it.matrix(), it.sym(), it.rhs(), refX, statFile);
 
    if (statFileExists) {
      std::ofstream statbuf(statFile.c_str(), std::ios::app);
      statbuf << "  <BEST_SOLVER ID='" << best_time_id << "'></BEST_SOLVER>\n";
      statbuf << " </LINEARSYSTEM> \n";
      statbuf.close();
    }
  }
}
 
bool get_options(int argc, char** args, string option, string* value = 0) {
  int idx = 1, found = false;
  while (idx < argc && !found) {
    if (option.compare(args[idx]) == 0) {
      found = true;
      if (value) *value = args[idx + 1];
    }
    idx += 2;
  }
  return found;
}