sparsemat.hpp

Go to the documentation of this file.

// Copyright (c) 2010, Lawrence Livermore National Security, LLC. Produced at
// the Lawrence Livermore National Laboratory. LLNL-CODE-443211. All Rights
// reserved. See file COPYRIGHT for details.
//
// This file is part of the MFEM library. For more information and source code
// availability see http://mfem.org.
//
// MFEM is free software; you can redistribute it and/or modify it under the
// terms of the GNU Lesser General Public License (as published by the Free
// Software Foundation) version 2.1 dated February 1999.

#ifndef MFEM_SPARSEMAT
#define MFEM_SPARSEMAT

// Data types for sparse matrix

#include "../general/mem_alloc.hpp"
#include "../general/table.hpp"
#include "densemat.hpp"
#include <iostream>

namespace mfem
{

class
#if defined(__alignas_is_defined)
   alignas(double)
#endif
   RowNode
{
public:
   double Value;
   RowNode *Prev;
   int Column;
};

class SparseMatrix : public AbstractSparseMatrix
{
private:

   int *I, *J;

   double *A;

   RowNode **Rows;

   mutable int current_row;
   mutable int* ColPtrJ;
   mutable RowNode ** ColPtrNode;

#ifdef MFEM_USE_MEMALLOC
   typedef MemAlloc <RowNode, 1024> RowNodeAlloc;
   RowNodeAlloc * NodesMem;
#endif

   bool ownGraph;
   bool ownData;

   bool isSorted;

   void Destroy();   // Delete all owned data
   void SetEmpty();  // Init all entries with empty values

public:
   SparseMatrix() { SetEmpty(); }

   explicit SparseMatrix(int nrows, int ncols = -1);

   SparseMatrix(int *i, int *j, double *data, int m, int n);

   SparseMatrix(int *i, int *j, double *data, int m, int n, bool ownij,
                bool owna, bool issorted);

   SparseMatrix(int nrows, int ncols, int rowsize);

   SparseMatrix(const SparseMatrix &mat, bool copy_graph = true);

   void MakeRef(const SparseMatrix &master);

   int Size() const { return Height(); }

   void Clear() { Destroy(); SetEmpty(); }

   bool Empty() { return (A == NULL) && (Rows == NULL); }

   inline int *GetI() const { return I; }
   inline int *GetJ() const { return J; }
   inline double *GetData() const { return A; }
   int RowSize(const int i) const;
   int MaxRowSize() const;
   int *GetRowColumns(const int row);
   const int *GetRowColumns(const int row) const;
   double *GetRowEntries(const int row);
   const double *GetRowEntries(const int row) const;


   void SetWidth(int width_ = -1);


   int ActualWidth();

   void SortColumnIndices();

   virtual double &Elem(int i, int j);

   virtual const double &Elem(int i, int j) const;

   double &operator()(int i, int j);

   const double &operator()(int i, int j) const;

   void GetDiag(Vector & d) const;

   virtual void Mult(const Vector &x, Vector &y) const;

   void AddMult(const Vector &x, Vector &y, const double a = 1.0) const;

   void MultTranspose(const Vector &x, Vector &y) const;

   void AddMultTranspose(const Vector &x, Vector &y,
                         const double a = 1.0) const;

   void PartMult(const Array<int> &rows, const Vector &x, Vector &y) const;
   void PartAddMult(const Array<int> &rows, const Vector &x, Vector &y,
                    const double a=1.0) const;

   void BooleanMult(const Array<int> &x, Array<int> &y) const;
   void BooleanMultTranspose(const Array<int> &x, Array<int> &y) const;

   double InnerProduct(const Vector &x, const Vector &y) const;

   void GetRowSums(Vector &x) const;
   double GetRowNorml1(int irow) const;

   virtual MatrixInverse *Inverse() const;

   void EliminateRow(int row, const double sol, Vector &rhs);

   void EliminateRow(int row, int setOneDiagonal = 0);
   void EliminateCol(int col);
   void EliminateCols(Array<int> &cols, Vector *x = NULL, Vector *b = NULL);

   void EliminateRowCol(int rc, const double sol, Vector &rhs, int d = 0);

   void EliminateRowColMultipleRHS(int rc, const Vector &sol,
                                   DenseMatrix &rhs, int d = 0);

   void EliminateRowCol(int rc, int d = 0);
   void EliminateRowColDiag(int rc, double value);
   // Same as above + save the eliminated entries in Ae so that
   // (*this) + Ae is the original matrix
   void EliminateRowCol(int rc, SparseMatrix &Ae, int d = 0);

   void SetDiagIdentity();
   void EliminateZeroRows();

   void Gauss_Seidel_forw(const Vector &x, Vector &y) const;
   void Gauss_Seidel_back(const Vector &x, Vector &y) const;

   double GetJacobiScaling() const;
   void Jacobi(const Vector &b, const Vector &x0, Vector &x1, double sc) const;

   void DiagScale(const Vector &b, Vector &x, double sc = 1.0) const;

   void Jacobi2(const Vector &b, const Vector &x0, Vector &x1,
                double sc = 1.0) const;

   void Jacobi3(const Vector &b, const Vector &x0, Vector &x1,
                double sc = 1.0) const;

   virtual void Finalize(int skip_zeros = 1);

   bool Finalized() const { return (A != NULL); }
   bool areColumnsSorted() const { return isSorted; }

   void GetBlocks(Array2D<SparseMatrix *> &blocks) const;

   void GetSubMatrix(const Array<int> &rows, const Array<int> &cols,
                     DenseMatrix &subm);

   inline void SetColPtr(const int row) const;
   inline void ClearColPtr() const;
   inline double &SearchRow(const int col);
   inline void _Add_(const int col, const double a)
   { SearchRow(col) += a; }
   inline void _Set_(const int col, const double a)
   { SearchRow(col) = a; }
   inline double _Get_(const int col) const;

   inline double &SearchRow(const int row, const int col);
   inline void _Add_(const int row, const int col, const double a)
   { SearchRow(row, col) += a; }
   inline void _Set_(const int row, const int col, const double a)
   { SearchRow(row, col) = a; }

   void Set(const int i, const int j, const double a);
   void Add(const int i, const int j, const double a);

   void SetSubMatrix(const Array<int> &rows, const Array<int> &cols,
                     const DenseMatrix &subm, int skip_zeros = 1);

   void SetSubMatrixTranspose(const Array<int> &rows, const Array<int> &cols,
                              const DenseMatrix &subm, int skip_zeros = 1);

   void AddSubMatrix(const Array<int> &rows, const Array<int> &cols,
                     const DenseMatrix &subm, int skip_zeros = 1);

   bool RowIsEmpty(const int row) const;

   virtual int GetRow(const int row, Array<int> &cols, Vector &srow) const;

   void SetRow(const int row, const Array<int> &cols, const Vector &srow);
   void AddRow(const int row, const Array<int> &cols, const Vector &srow);

   void ScaleRow(const int row, const double scale);
   // this = diag(sl) * this;
   void ScaleRows(const Vector & sl);
   // this = this * diag(sr);
   void ScaleColumns(const Vector & sr);

   SparseMatrix &operator+=(const SparseMatrix &B);

   void Add(const double a, const SparseMatrix &B);

   SparseMatrix &operator=(double a);

   SparseMatrix &operator*=(double a);

   void Print(std::ostream &out = std::cout, int width_ = 4) const;

   void PrintMatlab(std::ostream &out = std::cout) const;

   void PrintMM(std::ostream &out = std::cout) const;

   void PrintCSR(std::ostream &out) const;

   void PrintCSR2(std::ostream &out) const;

   int Walk(int &i, int &j, double &a);

   double IsSymmetric() const;

   void Symmetrize();

   virtual int NumNonZeroElems() const;

   double MaxNorm() const;

   int CountSmallElems(double tol) const;

   void SetGraphOwner(bool ownij) { ownGraph = ownij; }
   void SetDataOwner(bool owna) { ownData = owna; }
   bool OwnsGraph() const { return ownGraph; }
   bool OwnsData() const { return ownData; }
   void LoseData() { ownGraph = ownData = false; }

   void Swap(SparseMatrix &other);

   virtual ~SparseMatrix() { Destroy(); }
};

void SparseMatrixFunction(SparseMatrix &S, double (*f)(double));


SparseMatrix *Transpose(const SparseMatrix &A);
SparseMatrix *TransposeAbstractSparseMatrix (const AbstractSparseMatrix &A,
                                             int useActualWidth);

SparseMatrix *Mult(const SparseMatrix &A, const SparseMatrix &B,
                   SparseMatrix *OAB = NULL);

SparseMatrix *MultAbstractSparseMatrix (const AbstractSparseMatrix &A,
                                        const AbstractSparseMatrix &B);

DenseMatrix *Mult(const SparseMatrix &A, DenseMatrix &B);

DenseMatrix *RAP(const SparseMatrix &A, DenseMatrix &P);

SparseMatrix *RAP(const SparseMatrix &A, const SparseMatrix &R,
                  SparseMatrix *ORAP = NULL);

SparseMatrix *RAP(const SparseMatrix &Rt, const SparseMatrix &A,
                  const SparseMatrix &P);

SparseMatrix *Mult_AtDA(const SparseMatrix &A, const Vector &D,
                        SparseMatrix *OAtDA = NULL);


SparseMatrix * Add(const SparseMatrix & A, const SparseMatrix & B);
SparseMatrix * Add(double a, const SparseMatrix & A, double b,
                   const SparseMatrix & B);
SparseMatrix * Add(Array<SparseMatrix *> & Ai);


// Inline methods

inline void SparseMatrix::SetColPtr(const int row) const
{
   if (Rows)
   {
      if (ColPtrNode == NULL)
      {
         ColPtrNode = new RowNode *[width];
         for (int i = 0; i < width; i++)
         {
            ColPtrNode[i] = NULL;
         }
      }
      for (RowNode *node_p = Rows[row]; node_p != NULL; node_p = node_p->Prev)
      {
         ColPtrNode[node_p->Column] = node_p;
      }
   }
   else
   {
      if (ColPtrJ == NULL)
      {
         ColPtrJ = new int[width];
         for (int i = 0; i < width; i++)
         {
            ColPtrJ[i] = -1;
         }
      }
      for (int j = I[row], end = I[row+1]; j < end; j++)
      {
         ColPtrJ[J[j]] = j;
      }
   }
   current_row = row;
}

inline void SparseMatrix::ClearColPtr() const
{
   if (Rows)
      for (RowNode *node_p = Rows[current_row]; node_p != NULL;
           node_p = node_p->Prev)
      {
         ColPtrNode[node_p->Column] = NULL;
      }
   else
      for (int j = I[current_row], end = I[current_row+1]; j < end; j++)
      {
         ColPtrJ[J[j]] = -1;
      }
}

inline double &SparseMatrix::SearchRow(const int col)
{
   if (Rows)
   {
      RowNode *node_p = ColPtrNode[col];
      if (node_p == NULL)
      {
#ifdef MFEM_USE_MEMALLOC
         node_p = NodesMem->Alloc();
#else
         node_p = new RowNode;
#endif
         node_p->Prev = Rows[current_row];
         node_p->Column = col;
         node_p->Value = 0.0;
         Rows[current_row] = ColPtrNode[col] = node_p;
      }
      return node_p->Value;
   }
   else
   {
      const int j = ColPtrJ[col];
      MFEM_VERIFY(j != -1, "Entry for column " << col << " is not allocated.");
      return A[j];
   }
}

inline double SparseMatrix::_Get_(const int col) const
{
   if (Rows)
   {
      RowNode *node_p = ColPtrNode[col];
      return (node_p == NULL) ? 0.0 : node_p->Value;
   }
   else
   {
      const int j = ColPtrJ[col];
      return (j == -1) ? 0.0 : A[j];
   }
}

inline double &SparseMatrix::SearchRow(const int row, const int col)
{
   if (Rows)
   {
      RowNode *node_p;

      for (node_p = Rows[row]; 1; node_p = node_p->Prev)
      {
         if (node_p == NULL)
         {
#ifdef MFEM_USE_MEMALLOC
            node_p = NodesMem->Alloc();
#else
            node_p = new RowNode;
#endif
            node_p->Prev = Rows[row];
            node_p->Column = col;
            node_p->Value = 0.0;
            Rows[row] = node_p;
            break;
         }
         else if (node_p->Column == col)
         {
            break;
         }
      }
      return node_p->Value;
   }
   else
   {
      int *Ip = I+row, *Jp = J;
      for (int k = Ip[0], end = Ip[1]; k < end; k++)
      {
         if (Jp[k] == col)
         {
            return A[k];
         }
      }
      MFEM_ABORT("Could not find entry for row = " << row << ", col = " << col);
   }
   return A[0];
}

template<> inline void Swap<SparseMatrix>(SparseMatrix &a, SparseMatrix &b)
{
   a.Swap(b);
}

}

#endif