dolfin team mailing list archive

[Kent Andre <kent-and@xxxxxxxxx>]

Hi, 

Mikael Mortensen has written a function compress_sparse for removing all
the non-zeros in a Matrix. There can be many! For instance for 
a vector mass or stiffness matrix in 3D, 2/3 or more of the matrix
entries are zeros. Naturally, in such applications, we get a big speed
up. 

Mikael has put this function in GenericMatrix. Is this the right place? 
Should a new matrix be made instead ?

The only side effect I can think of is that the sparsity pattern is
changed. Hence, the matrix may no longer be added to another 
matrix created using the same function space.  

Kent
 

// Copyright (C) 2006-2009 Garth N. Wells.
// Licensed under the GNU LGPL Version 2.1.
//
// Modified by Johan Jansson, 2006.
// Modified by Anders Logg, 2006-2008.
// Modified by Ola Skavhaug, 2007-2008.
// Modified by Kent-Andre Mardal, 2008.
// Modified by Martin Alnæs, 2008.
//
// First added:  2006-04-24
// Last changed: 2009-09-08

#ifndef __GENERIC_MATRIX_H
#define __GENERIC_MATRIX_H

#include <tr1/tuple>
#include <vector>
#include "GenericTensor.h"

//
#include "SparsityPattern.h"
#include "GenericSparsityPattern.h"
#include <dolfin/fem/SparsityPatternBuilder.h>
#include <dolfin/common/Timer.h>

namespace dolfin
{

  class GenericVector;
  class XMLMatrix;

  /// This class defines a common interface for matrices.

  class GenericMatrix : public GenericTensor
  {
  public:

    /// Destructor
    virtual ~GenericMatrix() {}

    //--- Implementation of the GenericTensor interface ---

    /// Resize tensor with given dimensions
    virtual void resize(uint rank, const uint* dims)
    { assert(rank == 2); resize(dims[0], dims[1]); }

    /// Initialize zero tensor using sparsity pattern
    virtual void init(const GenericSparsityPattern& sparsity_pattern) = 0;

    /// Return copy of tensor
    virtual GenericMatrix* copy() const = 0;

    /// Return tensor rank (number of dimensions)
    virtual uint rank() const
    { return 2; }

    /// Return size of given dimension
    virtual uint size(uint dim) const = 0;

    /// Get block of values
    virtual void get(double* block, const uint* num_rows,
                     const uint * const * rows) const
    { get(block, num_rows[0], rows[0], num_rows[1], rows[1]); }

    /// Set block of values
    virtual void set(const double* block, const uint* num_rows,
                     const uint * const * rows)
    { set(block, num_rows[0], rows[0], num_rows[1], rows[1]); }

    /// Add block of values
    virtual void add(const double* block, const uint* num_rows,
                     const uint * const * rows)
    { add(block, num_rows[0], rows[0], num_rows[1], rows[1]); }

    /// Set all entries to zero and keep any sparse structure
    virtual void zero() = 0;

    /// Finalize assembly of tensor
    virtual void apply() = 0;

    /// Return informal string representation (pretty-print)
    virtual std::string str(bool verbose) const = 0;

    //--- Matrix interface ---

    /// Resize matrix to  M x N
    virtual void resize(uint M, uint N) = 0;

    /// Get block of values
    virtual void get(double* block, uint m, const uint* rows, uint n,
                     const uint* cols) const = 0;

    /// Set block of values
    virtual void set(const double* block, uint m, const uint* rows, uint n,
                     const uint* cols) = 0;

    /// Add block of values
    virtual void add(const double* block, uint m, const uint* rows, uint n,
                     const uint* cols) = 0;

    /// Add multiple of given matrix (AXPY operation)
    virtual void axpy(double a, const GenericMatrix& A,
                      bool same_nonzero_pattern) = 0;

    /// Return norm of matrix
    virtual double norm(std::string norm_type) const = 0;

    /// Get non-zero values of given row
    virtual void getrow(uint row, std::vector<uint>& columns,
                        std::vector<double>& values) const = 0;

    /// Set values for given row
    virtual void setrow(uint row, const std::vector<uint>& columns,
                        const std::vector<double>& values) = 0;

    /// Set given rows to zero
    virtual void zero(uint m, const uint* rows) = 0;

    /// Set given rows to identity matrix
    virtual void ident(uint m, const uint* rows) = 0;

    /// Matrix-vector product, y = Ax
    virtual void mult(const GenericVector& x, GenericVector& y) const = 0;

    /// Matrix-vector product, y = A^T x
    virtual void transpmult(const GenericVector& x, GenericVector& y) const = 0;

    /// Multiply matrix by given number
    virtual const GenericMatrix& operator*= (double a) = 0;

    /// Divide matrix by given number
    virtual const GenericMatrix& operator/= (double a) = 0;

    /// Add given matrix
    const GenericMatrix& operator+= (const GenericMatrix& A)
    {
      axpy(1.0, A, false);
      return *this;
    }

    /// Subtract given matrix
    const GenericMatrix& operator-= (const GenericMatrix& A)
    {
      axpy(-1.0, A, false);
      return *this;
    }

    /// Assignment operator
    virtual const GenericMatrix& operator= (const GenericMatrix& x) = 0;

    /// Return pointers to underlying compresssed row/column storage data
    /// For compressed row storage, data = (row_pointer[#rows +1],
    /// column_index[#nz], matrix_values[#nz], nz)
    virtual std::tr1::tuple<const std::size_t*, const std::size_t*,
                                            const double*, int> data() const
    {
      error("Unable to return pointers to underlying matrix data.");
      return std::tr1::tuple<const std::size_t*, const std::size_t*,
                                               const double*, int>(0, 0, 0, 0);
    }

    //--- Convenience functions ---

    /// Get value of given entry
    virtual double operator() (uint i, uint j) const
    { double value(0); get(&value, 1, &i, 1, &j); return value; }

    /// Get value of given entry
    virtual double getitem(std::pair<uint, uint> ij) const
    { double value(0); get(&value, 1, &ij.first, 1, &ij.second); return value; }

    /// Set given entry to value
    virtual void setitem(std::pair<uint, uint> ij, double value)
    { set(&value, 1, &ij.first, 1, &ij.second); }
    
    typedef XMLMatrix XMLHandler;

    void compress_sparse()
    {
      GenericMatrix* B;
    
      Timer timer("Compress matrix ");
    
      // Make a copy of this because (*this) will be zeroed when recreated with a new sparsity pattern
      B = (*this).copy();
    
      // New sparsity pattern
      GenericSparsityPattern* new_sparsity_pattern = new SparsityPattern(SparsityPattern::unsorted);
    
      uint* global_dimensions = new uint[2];   
      global_dimensions[0] = this->size(0);
      global_dimensions[1] = this->size(1);
      const uint N = global_dimensions[0];

      new_sparsity_pattern->init(2, global_dimensions);

      std::vector<uint> columns;
      std::vector<double> values;
      std::vector<uint> newcounts(N);
      uint* num_rows = new uint[2];
      uint count = 0;
      num_rows[0] = 1;
    
      uint** dofs = new uint*[2];
      dofs[0] = new uint[1];
      dofs[1] = new uint[N];
       
      for (uint i = 0; i < N; i++)
      {
        // Get row and locate nonzeros
        this->getrow(i, columns, values);
        count = 0;
        for (uint j = 0; j < columns.size(); j++)
        {
          if(values[j]*values[j] > 1.e-32)
          {    
            dofs[1][count]=columns[j];
            count++;
          }
        }
        newcounts[i]=count;
        dofs[0][0] = i;
        num_rows[1] = count;
        
        // Build new improved sparsity pattern
        new_sparsity_pattern->insert(num_rows,dofs);
      }
      delete [] dofs[0];
      delete [] dofs[1];
      delete [] dofs;
        
      // Finalize sparsity pattern
      new_sparsity_pattern->apply();
    
      // Recreate with the new sparsity pattern. This is zeroed in the process.    
      this->init(*new_sparsity_pattern);
      delete new_sparsity_pattern;
    
      // Put the old values back
      uint* cols = new uint[N];
      double* vals = new double[N];
      num_rows[0]=1;
      for (uint i = 0; i < N; i++)
      {
        B->getrow(i, columns, values);
        count=0;
        for (uint j = 0; j < columns.size(); j++)
        {
          if(values[j]*values[j] > 1.e-32)
          {
            cols[count]=columns[j];
            vals[count]=values[j];
                count++;
          }
        }
        this->set(vals, 1, &i, count, cols);
      }
    
      delete [] cols;
      delete [] vals;
      delete [] num_rows;
    
      this->apply();
    }
    
  };
  

}
#endif