// SPDX-FileCopyrightText: Copyright © DUNE Project contributors, see file LICENSE.md in module root // SPDX-License-Identifier: LicenseRef-GPL-2.0-only-with-DUNE-exception // -*- tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*- // vi: set et ts=4 sw=2 sts=2: #ifndef DUNE_ISTL_MATRIXMATRIX_HH #define DUNE_ISTL_MATRIXMATRIX_HH #include #include #include #include namespace Dune { /** * @addtogroup ISTL_SPMV * * @{ */ /** @file * @author Markus Blatt * @brief provides functions for sparse matrix matrix multiplication. */ namespace { /** * @brief Traverses over the nonzero pattern of the matrix-matrix product. * * Template parameter b is used to select the matrix product: *
0
\f$A\cdot B\f$
*
1
\f$A^T\cdot B\f$
*
2
\f$A\cdot B^T\f$
*/ template struct NonzeroPatternTraverser {}; template<> struct NonzeroPatternTraverser<0> { template static void traverse(const Dune::BCRSMatrix,A1>& A, const Dune::BCRSMatrix,A2>& B, F& func) { if(A.M()!=B.N()) DUNE_THROW(ISTLError, "The sizes of the matrices do not match: "<,A1>::ConstRowIterator Row; typedef typename Dune::BCRSMatrix,A1>::ConstColIterator Col; typedef typename Dune::BCRSMatrix,A2>::ConstColIterator BCol; for(Row row= A.begin(); row != A.end(); ++row) { // Loop over all column entries for(Col col = row->begin(); col != row->end(); ++col) { // entry at i,k // search for all nonzeros in row k for(BCol bcol = B[col.index()].begin(); bcol != B[col.index()].end(); ++bcol) { func(*col, *bcol, row.index(), bcol.index()); } } } } }; template<> struct NonzeroPatternTraverser<1> { template static void traverse(const Dune::BCRSMatrix,A1>& A, const Dune::BCRSMatrix,A2>& B, F& func) { if(A.N()!=B.N()) DUNE_THROW(ISTLError, "The sizes of the matrices do not match: "<,A1>::ConstRowIterator Row; typedef typename Dune::BCRSMatrix,A1>::ConstColIterator Col; typedef typename Dune::BCRSMatrix,A2>::ConstColIterator BCol; for(Row row=A.begin(); row!=A.end(); ++row) { for(Col col=row->begin(); col!=row->end(); ++col) { for(BCol bcol = B[row.index()].begin(); bcol != B[row.index()].end(); ++bcol) { func(*col, *bcol, col.index(), bcol.index()); } } } } }; template<> struct NonzeroPatternTraverser<2> { template static void traverse(const BCRSMatrix,A1>& mat, const BCRSMatrix,A2>& matt, F& func) { if(mat.M()!=matt.M()) DUNE_THROW(ISTLError, "The sizes of the matrices do not match: "<,A1>::ConstRowIterator row_iterator; typedef typename BCRSMatrix,A1>::ConstColIterator col_iterator; typedef typename BCRSMatrix,A2>::ConstRowIterator row_iterator_t; typedef typename BCRSMatrix,A2>::ConstColIterator col_iterator_t; for(row_iterator mrow=mat.begin(); mrow != mat.end(); ++mrow) { //iterate over the column entries // mt is a transposed matrix crs therefore it is treated as a ccs matrix // and the row_iterator iterates over the columns of the transposed matrix. // search the row of the transposed matrix for an entry with the same index // as the mcol iterator for(row_iterator_t mtcol=matt.begin(); mtcol != matt.end(); ++mtcol) { //Search for col entries in mat that have a corresponding row index in matt // (i.e. corresponding col index in the as this is the transposed matrix col_iterator_t mtrow=mtcol->begin(); bool funcCalled = false; for(col_iterator mcol=mrow->begin(); mcol != mrow->end(); ++mcol) { // search // TODO: This should probably be substituted by a binary search for( ; mtrow != mtcol->end(); ++mtrow) if(mtrow.index()>=mcol.index()) break; if(mtrow != mtcol->end() && mtrow.index()==mcol.index()) { func(*mcol, *mtrow, mtcol.index()); funcCalled = true; // In some cases we only search for one pair, then we break here // and continue with the next column. if(F::do_break) break; } } // move on with func only if func was called, otherwise they might // get out of sync if (funcCalled) func.nextCol(); } func.nextRow(); } } }; template class SparsityPatternInitializer { public: enum {do_break=true}; typedef typename BCRSMatrix,A>::CreateIterator CreateIterator; typedef typename BCRSMatrix,A>::size_type size_type; SparsityPatternInitializer(CreateIterator iter) : rowiter(iter) {} template void operator()(const T1&, const T2&, size_type j) { rowiter.insert(j); } void nextRow() { ++rowiter; } void nextCol() {} private: CreateIterator rowiter; }; template class MatrixInitializer { public: enum {do_break=true}; typedef typename Dune::BCRSMatrix,TA> Matrix; typedef typename Matrix::CreateIterator CreateIterator; typedef typename Matrix::size_type size_type; MatrixInitializer(Matrix& A_, size_type) : count(0), A(A_) {} template void operator()(const T1&, const T2&, int) { ++count; } void nextCol() {} void nextRow() {} std::size_t nonzeros() { return count; } template void initPattern(const BCRSMatrix,A1>& mat1, const BCRSMatrix,A2>& mat2) { SparsityPatternInitializer sparsity(A.createbegin()); NonzeroPatternTraverser::traverse(mat1,mat2,sparsity); } private: std::size_t count; Matrix& A; }; template class MatrixInitializer<1,T,TA,n,m> { public: enum {do_break=false}; typedef Dune::BCRSMatrix,TA> Matrix; typedef typename Matrix::CreateIterator CreateIterator; typedef typename Matrix::size_type size_type; MatrixInitializer(Matrix& A_, size_type rows) : A(A_), entries(rows) {} template void operator()(const T1&, const T2&, size_type i, size_type j) { entries[i].insert(j); } void nextCol() {} size_type nonzeros() { size_type nnz=0; typedef typename std::vector >::const_iterator Iter; for(Iter iter = entries.begin(); iter != entries.end(); ++iter) nnz+=(*iter).size(); return nnz; } template void initPattern(const BCRSMatrix,A1>&, const BCRSMatrix,A2>&) { typedef typename std::vector >::const_iterator Iter; CreateIterator citer = A.createbegin(); for(Iter iter = entries.begin(); iter != entries.end(); ++iter, ++citer) { typedef std::set::const_iterator SetIter; for(SetIter index=iter->begin(); index != iter->end(); ++index) citer.insert(*index); } } private: Matrix& A; std::vector > entries; }; template struct MatrixInitializer<0,T,TA,n,m> : public MatrixInitializer<1,T,TA,n,m> { MatrixInitializer(Dune::BCRSMatrix,TA>& A_, typename Dune::BCRSMatrix,TA>::size_type rows) : MatrixInitializer<1,T,TA,n,m>(A_,rows) {} }; template void addMatMultTransposeMat(FieldMatrix& res, const FieldMatrix& mat, const FieldMatrix& matt) { typedef typename FieldMatrix::size_type size_type; for(size_type row=0; row void addTransposeMatMultMat(FieldMatrix& res, const FieldMatrix& mat, const FieldMatrix& matt) { typedef typename FieldMatrix::size_type size_type; for(size_type i=0; i void addMatMultMat(FieldMatrix& res, const FieldMatrix& mat, const FieldMatrix& matt) { typedef typename FieldMatrix::size_type size_type; for(size_type row=0; row class EntryAccumulatorFather { public: enum {do_break=false}; typedef BCRSMatrix,A> Matrix; typedef typename Matrix::RowIterator Row; typedef typename Matrix::ColIterator Col; EntryAccumulatorFather(Matrix& mat_) : mat(mat_), row(mat.begin()) { mat=0; col=row->begin(); } void nextRow() { ++row; if(row!=mat.end()) col=row->begin(); } void nextCol() { ++this->col; } protected: Matrix& mat; private: Row row; protected: Col col; }; template class EntryAccumulator : public EntryAccumulatorFather { public: typedef BCRSMatrix,A> Matrix; typedef typename Matrix::size_type size_type; EntryAccumulator(Matrix& mat_) : EntryAccumulatorFather(mat_) {} template void operator()(const T1& t1, const T2& t2, size_type i) { assert(this->col.index()==i); addMatMultMat(*(this->col),t1,t2); } }; template class EntryAccumulator : public EntryAccumulatorFather { public: typedef BCRSMatrix,A> Matrix; typedef typename Matrix::size_type size_type; EntryAccumulator(Matrix& mat_) : EntryAccumulatorFather(mat_) {} template void operator()(const T1& t1, const T2& t2, size_type i, size_type j) { addMatMultMat(this->mat[i][j], t1, t2); } }; template class EntryAccumulator : public EntryAccumulatorFather { public: typedef BCRSMatrix,A> Matrix; typedef typename Matrix::size_type size_type; EntryAccumulator(Matrix& mat_) : EntryAccumulatorFather(mat_) {} template void operator()(const T1& t1, const T2& t2, size_type i, size_type j) { addTransposeMatMultMat(this->mat[i][j], t1, t2); } }; template class EntryAccumulator : public EntryAccumulatorFather { public: typedef BCRSMatrix,A> Matrix; typedef typename Matrix::size_type size_type; EntryAccumulator(Matrix& mat_) : EntryAccumulatorFather(mat_) {} template void operator()(const T1& t1, const T2& t2, [[maybe_unused]] size_type i) { assert(this->col.index()==i); addMatMultTransposeMat(*this->col,t1,t2); } }; template struct SizeSelector {}; template<> struct SizeSelector<0> { template static std::tuple size(const M1& m1, const M2& m2) { return std::make_tuple(m1.N(), m2.M()); } }; template<> struct SizeSelector<1> { template static std::tuple size(const M1& m1, const M2& m2) { return std::make_tuple(m1.M(), m2.M()); } }; template<> struct SizeSelector<2> { template static std::tuple size(const M1& m1, const M2& m2) { return std::make_tuple(m1.N(), m2.N()); } }; template void matMultMat(BCRSMatrix,A>& res, const BCRSMatrix,A1>& mat1, const BCRSMatrix,A2>& mat2) { // First step is to count the number of nonzeros typename BCRSMatrix,A>::size_type rows, cols; std::tie(rows,cols)=SizeSelector::size(mat1, mat2); MatrixInitializer patternInit(res, rows); Timer timer; NonzeroPatternTraverser::traverse(mat1,mat2,patternInit); res.setSize(rows, cols, patternInit.nonzeros()); res.setBuildMode(BCRSMatrix,A>::row_wise); //std::cout<<"Counting nonzeros took "< entriesAccu(res); NonzeroPatternTraverser::traverse(mat1,mat2,entriesAccu); //std::cout<<"Calculating entries took "< struct MatMultMatResult {}; template struct MatMultMatResult,FieldMatrix > { typedef FieldMatrix type; }; template struct MatMultMatResult,A >,BCRSMatrix,A1 > > { typedef BCRSMatrix,FieldMatrix >::type, std::allocator,FieldMatrix >::type> > type; }; /** * @brief Helper TMP to get the result type of a sparse matrix matrix multiplication (\f$C=A*B\f$) * * The type of matrix C will be stored as the associated type MatMultMatResult::type. * @tparam M1 The type of matrix A. * @tparam M2 The type of matrix B. */ template struct TransposedMatMultMatResult {}; template struct TransposedMatMultMatResult,FieldMatrix > { typedef FieldMatrix type; }; template struct TransposedMatMultMatResult,A >,BCRSMatrix,A1 > > { typedef BCRSMatrix,FieldMatrix >::type, std::allocator,FieldMatrix >::type> > type; }; /** * @brief Calculate product of a sparse matrix with a transposed sparse matrices (\f$C=A*B^T\f$). * * @param res Matrix for the result of the computation. * @param mat Matrix A. * @param matt Matrix B, which will be transposed before the multiplication. * @param tryHard ignored */ template void matMultTransposeMat(BCRSMatrix,A>& res, const BCRSMatrix,A1>& mat, const BCRSMatrix,A2>& matt, bool /*tryHard*/=false) { matMultMat<2>(res,mat, matt); } /** * @brief Calculate product of two sparse matrices (\f$C=A*B\f$). * * @param res Matrix for the result of the computation. * @param mat Matrix A. * @param matt Matrix B. * @param tryHard ignored */ template void matMultMat(BCRSMatrix,A>& res, const BCRSMatrix,A1>& mat, const BCRSMatrix,A2>& matt, bool /*tryHard*/=false) { matMultMat<0>(res,mat, matt); } /** * @brief Calculate product of a transposed sparse matrix with another sparse matrices (\f$C=A^T*B\f$). * * @param res Matrix for the result of the computation. * @param mat Matrix A, which will be transposed before the multiplication. * @param matt Matrix B. * @param tryHard ignored */ template void transposeMatMultMat(BCRSMatrix,A>& res, const BCRSMatrix,A1>& mat, const BCRSMatrix,A2>& matt, bool /*tryHard*/=false) { matMultMat<1>(res,mat, matt); } } #endif