// ------------------------------------------------------------------------ // // SPDX-License-Identifier: LGPL-2.1-or-later // Copyright (C) 2008 - 2025 by the deal.II authors // // This file is part of the deal.II library. // // Part of the source code is dual licensed under Apache-2.0 WITH // LLVM-exception OR LGPL-2.1-or-later. Detailed license information // governing the source code and code contributions can be found in // LICENSE.md and CONTRIBUTING.md at the top level directory of deal.II. // // ------------------------------------------------------------------------ #ifndef dealii_chunk_sparse_matrix_h #define dealii_chunk_sparse_matrix_h #include #include #include #include #include #include #include #include DEAL_II_NAMESPACE_OPEN // Forward declarations #ifndef DOXYGEN template class Vector; template class FullMatrix; #endif /** * @addtogroup Matrix1 * @{ */ /** * A namespace in which we declare iterators over the elements of sparse * matrices. */ namespace ChunkSparseMatrixIterators { // forward declaration template class Iterator; /** * General template for sparse matrix accessors. The first template argument * denotes the underlying numeric type, the second the constness of the * matrix. * * The general template is not implemented, only the specializations for the * two possible values of the second template argument. Therefore, the * interface listed here only serves as a template provided since doxygen * does not link the specializations. */ template class Accessor : public ChunkSparsityPatternIterators::Accessor { public: /** * Value of this matrix entry. */ number value() const; /** * Value of this matrix entry. */ number & value(); /** * Return a reference to the matrix into which this accessor points. Note * that in the present case, this is a constant reference. */ const ChunkSparseMatrix & get_matrix() const; }; /** * Accessor class for constant matrices, used in the const_iterators. This * class builds on the accessor classes used for sparsity patterns to loop * over all nonzero entries, and only adds the accessor functions to gain * access to the actual value stored at a certain location. */ template class Accessor : public ChunkSparsityPatternIterators::Accessor { public: /** * Typedef for the type (including constness) of the matrix to be used * here. */ using MatrixType = const ChunkSparseMatrix; /** * Constructor. */ Accessor(MatrixType *matrix, const unsigned int row); /** * Constructor. Construct the end accessor for the given matrix. */ Accessor(MatrixType *matrix); /** * Copy constructor to get from a non-const accessor to a const accessor. */ Accessor(const ChunkSparseMatrixIterators::Accessor &a); /** * Value of this matrix entry. */ number value() const; /** * Return a reference to the matrix into which this accessor points. Note * that in the present case, this is a constant reference. */ const MatrixType & get_matrix() const; private: /** * Pointer to the matrix we use. */ MatrixType *matrix; /** * Make the advance function of the base class available. */ using ChunkSparsityPatternIterators::Accessor::advance; // Make iterator class a friend. template friend class Iterator; }; /** * Accessor class for non-constant matrices, used in the iterators. This * class builds on the accessor classes used for sparsity patterns to loop * over all nonzero entries, and only adds the accessor functions to gain * access to the actual value stored at a certain location. */ template class Accessor : public ChunkSparsityPatternIterators::Accessor { private: /** * Reference class. This is what the accessor class returns when you call * the value() function. The reference acts just as if it were a reference * to the actual value of a matrix entry, i.e. you can read and write it, * you can add and multiply to it, etc, but since the matrix does not give * away the address of this matrix entry, we have to go through functions * to do all this. * * The constructor takes a pointer to an accessor object that describes * which element of the matrix it points to. This creates an ambiguity * when one writes code like iterator->value()=0 (instead of * iterator->value()=0.0), since the right hand side is an integer that * can both be converted to a number (i.e., most commonly a * double) or to another object of type Reference. The compiler * then complains about not knowing which conversion to take. * * For some reason, adding another overload operator=(int) doesn't seem to * cure the problem. We avoid it, however, by adding a second, dummy * argument to the Reference constructor, that is unused, but makes sure * there is no second matching conversion sequence using a one-argument * right hand side. */ class Reference { public: /** * Constructor. For the second argument, see the general class * documentation. */ Reference(const Accessor *accessor, const bool dummy); /** * Conversion operator to the data type of the matrix. */ operator number() const; /** * Set the element of the matrix we presently point to to @p n. */ const Reference & operator=(const number n) const; /** * Add @p n to the element of the matrix we presently point to. */ const Reference & operator+=(const number n) const; /** * Subtract @p n from the element of the matrix we presently point to. */ const Reference & operator-=(const number n) const; /** * Multiply the element of the matrix we presently point to by @p n. */ const Reference & operator*=(const number n) const; /** * Divide the element of the matrix we presently point to by @p n. */ const Reference & operator/=(const number n) const; private: /** * Pointer to the accessor that denotes which element we presently point * to. */ const Accessor *accessor; }; public: /** * Typedef for the type (including constness) of the matrix to be used * here. */ using MatrixType = ChunkSparseMatrix; /** * Constructor. */ Accessor(MatrixType *matrix, const unsigned int row); /** * Constructor. Construct the end accessor for the given matrix. */ Accessor(MatrixType *matrix); /** * Value of this matrix entry, returned as a read- and writable reference. */ Reference value() const; /** * Return a reference to the matrix into which this accessor points. Note * that in the present case, this is a non-constant reference. */ MatrixType & get_matrix() const; private: /** * Pointer to the matrix we use. */ MatrixType *matrix; /** * Make the advance function of the base class available. */ using ChunkSparsityPatternIterators::Accessor::advance; // Make iterator class a friend. template friend class Iterator; }; /** * Iterator for constant and non-constant matrices. * * The first template argument denotes the underlying numeric type, the * second the constness of the matrix. * * Since there is a specialization of this class for * Constness=false, this class is for iterators to constant * matrices. */ template class Iterator { public: /** * Typedef for the matrix type (including constness) we are to operate on. */ using MatrixType = typename Accessor::MatrixType; /** * An alias for the type you get when you dereference an iterator of the * current kind. */ using value_type = const Accessor &; /** * A type that denotes what data types is used to express the difference * between two iterators. */ using difference_type = types::global_dof_index; /** * Constructor. Create an iterator into the matrix @p matrix for the given * row and the index within it. */ Iterator(MatrixType *matrix, const unsigned int row); /** * Constructor. Create the end iterator for the given matrix. */ Iterator(MatrixType *matrix); /** * Conversion constructor to get from a non-const iterator to a const * iterator. */ Iterator(const ChunkSparseMatrixIterators::Iterator &i); /** * Prefix increment. */ Iterator & operator++(); /** * Postfix increment. */ Iterator operator++(int); /** * Dereferencing operator. */ const Accessor & operator*() const; /** * Dereferencing operator. */ const Accessor * operator->() const; /** * Comparison. True, if both iterators point to the same matrix position. */ bool operator==(const Iterator &) const; /** * Inverse of ==. */ bool operator!=(const Iterator &) const; /** * Comparison operator. Result is true if either the first row number is * smaller or if the row numbers are equal and the first index is smaller. * * This function is only valid if both iterators point into the same * matrix. */ bool operator<(const Iterator &) const; /** * Comparison operator. Works in the same way as above operator, just the * other way round. */ bool operator>(const Iterator &) const; /** * Return the distance between the current iterator and the argument. The * distance is given by how many times one has to apply operator++ to the * current iterator to get the argument (for a positive return value), or * operator-- (for a negative return value). */ int operator-(const Iterator &p) const; /** * Return an iterator that is @p n ahead of the current one. */ Iterator operator+(const unsigned int n) const; private: /** * Store an object of the accessor class. */ Accessor accessor; }; } // namespace ChunkSparseMatrixIterators DEAL_II_NAMESPACE_CLOSE // Do not convert for module purposes namespace std { template struct iterator_traits< dealii::ChunkSparseMatrixIterators::Iterator> { using iterator_category = forward_iterator_tag; using value_type = typename dealii::ChunkSparseMatrixIterators:: Iterator::value_type; using difference_type = typename dealii::ChunkSparseMatrixIterators:: Iterator::difference_type; }; } // namespace std DEAL_II_NAMESPACE_OPEN // Do not convert for module purposes /** * Sparse matrix. This class implements the function to store values in the * locations of a sparse matrix denoted by a SparsityPattern. The separation * of sparsity pattern and values is done since one can store data elements of * different type in these locations without the SparsityPattern having to * know this, and more importantly one can associate more than one matrix with * the same sparsity pattern. * * The use of this class is demonstrated in step-51. * * @note Instantiations for this template are provided for @ and * @; others can be generated in application programs (see the * section on * @ref Instantiations * in the manual). */ template class ChunkSparseMatrix : public virtual EnableObserverPointer { public: /** * Declare the type for container size. */ using size_type = types::global_dof_index; /** * Type of matrix entries. This alias is analogous to value_type * in the standard library containers. */ using value_type = number; /** * Declare a type that has holds real-valued numbers with the same precision * as the template argument to this class. If the template argument of this * class is a real data type, then real_type equals the template argument. * If the template argument is a std::complex type then real_type equals the * type underlying the complex numbers. * * This alias is used to represent the return type of norms. */ using real_type = typename numbers::NumberTraits::real_type; /** * Typedef of an iterator class walking over all the nonzero entries of this * matrix. This iterator cannot change the values of the matrix. */ using const_iterator = ChunkSparseMatrixIterators::Iterator; /** * Typedef of an iterator class walking over all the nonzero entries of this * matrix. This iterator @em can change the values of the matrix, but of * course can't change the sparsity pattern as this is fixed once a sparse * matrix is attached to it. */ using iterator = ChunkSparseMatrixIterators::Iterator; /** * A structure that describes some of the traits of this class in terms of * its run-time behavior. Some other classes (such as the block matrix * classes) that take one or other of the matrix classes as its template * parameters can tune their behavior based on the variables in this class. */ struct Traits { /** * It is safe to elide additions of zeros to individual elements of this * matrix. */ static const bool zero_addition_can_be_elided = true; }; /** * @name Constructors and initialization. */ /** @{ */ /** * Constructor; initializes the matrix to be empty, without any structure, * i.e. the matrix is not usable at all. This constructor is therefore only * useful for matrices which are members of a class. All other matrices * should be created at a point in the data flow where all necessary * information is available. * * You have to initialize the matrix before usage with reinit(const * ChunkSparsityPattern&). */ ChunkSparseMatrix(); /** * Copy constructor. This constructor is only allowed to be called if the * matrix to be copied is empty. This is for the same reason as for the * ChunkSparsityPattern, see there for the details. * * If you really want to copy a whole matrix, you can do so by using the * copy_from() function. */ ChunkSparseMatrix(const ChunkSparseMatrix &); /** * Constructor. Takes the given matrix sparsity structure to represent the * sparsity pattern of this matrix. You can change the sparsity pattern * later on by calling the reinit(const ChunkSparsityPattern&) function. * * You have to make sure that the lifetime of the sparsity structure is at * least as long as that of this matrix or as long as reinit(const * ChunkSparsityPattern&) is not called with a new sparsity pattern. * * The constructor is marked explicit so as to disallow that someone passes * a sparsity pattern in place of a sparse matrix to some function, where an * empty matrix would be generated then. */ explicit ChunkSparseMatrix(const ChunkSparsityPattern &sparsity); /** * Copy constructor: initialize the matrix with the identity matrix. This * constructor will throw an exception if the sizes of the sparsity pattern * and the identity matrix do not coincide, or if the sparsity pattern does * not provide for nonzero entries on the entire diagonal. */ ChunkSparseMatrix(const ChunkSparsityPattern &sparsity, const IdentityMatrix &id); /** * Destructor. Free all memory, but do not release the memory of the * sparsity structure. */ virtual ~ChunkSparseMatrix() override; /** * Copy operator. Since copying entire sparse matrices is a very expensive * operation, we disallow doing so except for the special case of empty * matrices of size zero. This doesn't seem particularly useful, but is * exactly what one needs if one wanted to have a * std::vector@ @>: in that case, * one can create a vector (which needs the ability to copy objects) of * empty matrices that are then later filled with something useful. */ ChunkSparseMatrix & operator=(const ChunkSparseMatrix &); /** * Copy operator: initialize the matrix with the identity matrix. This * operator will throw an exception if the sizes of the sparsity pattern and * the identity matrix do not coincide, or if the sparsity pattern does not * provide for nonzero entries on the entire diagonal. */ ChunkSparseMatrix & operator=(const IdentityMatrix &id); /** * This operator assigns a scalar to a matrix. Since this does usually not * make much sense (should we set all matrix entries to this value? Only * the nonzero entries of the sparsity pattern?), this operation is only * allowed if the actual value to be assigned is zero. This operator only * exists to allow for the obvious notation matrix=0, which sets * all elements of the matrix to zero, but keep the sparsity pattern * previously used. */ ChunkSparseMatrix & operator=(const double d); /** * Reinitialize the sparse matrix with the given sparsity pattern. The * latter tells the matrix how many nonzero elements there need to be * reserved. * * Regarding memory allocation, the same applies as said above. * * You have to make sure that the lifetime of the sparsity structure is at * least as long as that of this matrix or as long as reinit(const * ChunkSparsityPattern &) is not called with a new sparsity structure. * * The elements of the matrix are set to zero by this function. */ virtual void reinit(const ChunkSparsityPattern &sparsity); /** * Release all memory and return to a state just like after having called * the default constructor. It also forgets the sparsity pattern it was * previously tied to. */ virtual void clear(); /** @} */ /** * @name Information on the matrix */ /** @{ */ /** * Return whether the object is empty. It is empty if either both dimensions * are zero or no ChunkSparsityPattern is associated. */ bool empty() const; /** * Return the dimension of the codomain (or range) space. Note that the * matrix is of dimension $m \times n$. */ size_type m() const; /** * Return the dimension of the domain space. Note that the matrix is of * dimension $m \times n$. */ size_type n() const; /** * Return the number of nonzero elements of this matrix. Actually, it * returns the number of entries in the sparsity pattern; if any of the * entries should happen to be zero, it is counted anyway. */ size_type n_nonzero_elements() const; /** * Return the number of actually nonzero elements of this matrix. * * Note, that this function does (in contrary to n_nonzero_elements()) not * count all entries of the sparsity pattern but only the ones that are * nonzero. */ size_type n_actually_nonzero_elements() const; /** * Return a (constant) reference to the underlying sparsity pattern of this * matrix. * * Though the return value is declared const, you should be aware * that it may change if you call any nonconstant function of objects which * operate on it. */ const ChunkSparsityPattern & get_sparsity_pattern() const; /** * Determine an estimate for the memory consumption (in bytes) of this * object. See MemoryConsumption. */ std::size_t memory_consumption() const; /** @} */ /** * @name Modifying entries */ /** @{ */ /** * Set the element (i,j) to value. Throws an error if the * entry does not exist or if value is not a finite number. Still, * it is allowed to store zero values in non-existent fields. */ void set(const size_type i, const size_type j, const number value); /** * Add value to the element (i,j). Throws an error if the * entry does not exist or if value is not a finite number. Still, * it is allowed to store zero values in non-existent fields. */ void add(const size_type i, const size_type j, const number value); /** * Add an array of values given by values in the given global * matrix row at columns specified by col_indices in the sparse matrix. * * The optional parameter elide_zero_values can be used to specify * whether zero values should be added anyway or these should be filtered * away and only non-zero data is added. The default value is true, * i.e., zero values won't be added into the matrix. */ template void add(const size_type row, const size_type n_cols, const size_type *col_indices, const number2 *values, const bool elide_zero_values = true, const bool col_indices_are_sorted = false); /** * Multiply the entire matrix by a fixed factor. */ ChunkSparseMatrix & operator*=(const number factor); /** * Divide the entire matrix by a fixed factor. */ ChunkSparseMatrix & operator/=(const number factor); /** * Symmetrize the matrix by forming the mean value between the existing * matrix and its transpose, $A = \frac 12(A+A^T)$. * * This operation assumes that the underlying sparsity pattern represents a * symmetric object. If this is not the case, then the result of this * operation will not be a symmetric matrix, since it only explicitly * symmetrizes by looping over the lower left triangular part for efficiency * reasons; if there are entries in the upper right triangle, then these * elements are missed in the symmetrization. Symmetrization of the sparsity * pattern can be obtain by ChunkSparsityPattern::symmetrize(). */ void symmetrize(); /** * Copy the matrix given as argument into the current object. * * Copying matrices is an expensive operation that we do not want to happen * by accident through compiler generated code for operator=. * (This would happen, for example, if one accidentally declared a function * argument of the current type by value rather than by * reference.) The functionality of copying matrices is implemented in * this member function instead. All copy operations of objects of this type * therefore require an explicit function call. * * The source matrix may be a matrix of arbitrary type, as long as its data * type is convertible to the data type of this matrix. * * The function returns a reference to *this. */ template ChunkSparseMatrix & copy_from(const ChunkSparseMatrix &source); /** * This function is complete analogous to the * ChunkSparsityPattern::copy_from() function in that it allows to * initialize a whole matrix in one step. See there for more information on * argument types and their meaning. You can also find a small example on * how to use this function there. * * The only difference to the cited function is that the objects which the * inner iterator points to need to be of type std::pair, where value needs to be convertible to the element * type of this class, as specified by the number template * argument. * * Previous content of the matrix is overwritten. Note that the entries * specified by the input parameters need not necessarily cover all elements * of the matrix. Elements not covered remain untouched. */ template void copy_from(const ForwardIterator begin, const ForwardIterator end); /** * Copy the nonzero entries of a full matrix into this object. Previous * content is deleted. Note that the underlying sparsity pattern must be * appropriate to hold the nonzero entries of the full matrix. */ template void copy_from(const FullMatrix &matrix); /** * Add matrix scaled by factor to this matrix, i.e. the * matrix factor*matrix is added to this. This function * throws an error if the sparsity patterns of the two involved matrices do * not point to the same object, since in this case the operation is * cheaper. * * The source matrix may be a sparse matrix over an arbitrary underlying * scalar type, as long as its data type is convertible to the data type of * this matrix. */ template void add(const number factor, const ChunkSparseMatrix &matrix); /** @} */ /** * @name Entry Access */ /** @{ */ /** * Return the value of the entry (i,j). This may be an expensive * operation and you should always take care where to call this function. In * order to avoid abuse, this function throws an exception if the required * element does not exist in the matrix. * * In case you want a function that returns zero instead (for entries that * are not in the sparsity pattern of the matrix), use the el() function. * * If you are looping over all elements, consider using one of the iterator * classes instead, since they are tailored better to a sparse matrix * structure. */ number operator()(const size_type i, const size_type j) const; /** * This function is mostly like operator()() in that it returns the value of * the matrix entry (i,j). The only difference is that if this entry * does not exist in the sparsity pattern, then instead of raising an * exception, zero is returned. While this may be convenient in some cases, * note that it is simple to write algorithms that are slow compared to an * optimal solution, since the sparsity of the matrix is not used. * * If you are looping over all elements, consider using one of the iterator * classes instead, since they are tailored better to a sparse matrix * structure. */ number el(const size_type i, const size_type j) const; /** * Return the main diagonal element in the ith row. This function * throws an error if the matrix is not quadratic. * * This function is considerably faster than the operator()(), since for * quadratic matrices, the diagonal entry may be the first to be stored in * each row and access therefore does not involve searching for the right * column number. */ number diag_element(const size_type i) const; /** * Extracts a copy of the values and indices in the given matrix row. * * The user is expected to pass the length of the arrays column_indices and * values, which gives a means for checking that we do not write to * unallocated memory. This method is motivated by a similar method in * Trilinos row matrices and gives faster access to entries in the matrix as * compared to iterators which are quite slow for this matrix type. */ void extract_row_copy(const size_type row, const size_type array_length, size_type &row_length, size_type *column_indices, number *values) const; /** @} */ /** * @name Matrix vector multiplications */ /** @{ */ /** * Matrix-vector multiplication: let dst = M*src with M being * this matrix. * * Note that while this function can operate on all vectors that offer * iterator classes, it is only really effective for objects of type * @ref Vector. * For all classes for which iterating over elements, or random member * access is expensive, this function is not efficient. In particular, if * you want to multiply with BlockVector objects, you should consider using * a BlockChunkSparseMatrix as well. * * Source and destination must not be the same vector. */ template void vmult(OutVector &dst, const InVector &src) const; /** * Matrix-vector multiplication: let dst = MT*src with * M being this matrix. This function does the same as vmult() but * takes the transposed matrix. * * Note that while this function can operate on all vectors that offer * iterator classes, it is only really effective for objects of type * @ref Vector. * For all classes for which iterating over elements, or random member * access is expensive, this function is not efficient. In particular, if * you want to multiply with BlockVector objects, you should consider using * a BlockChunkSparseMatrix as well. * * Source and destination must not be the same vector. */ template void Tvmult(OutVector &dst, const InVector &src) const; /** * Adding Matrix-vector multiplication. Add M*src on dst with * M being this matrix. * * Note that while this function can operate on all vectors that offer * iterator classes, it is only really effective for objects of type * @ref Vector. * For all classes for which iterating over elements, or random member * access is expensive, this function is not efficient. In particular, if * you want to multiply with BlockVector objects, you should consider using * a BlockChunkSparseMatrix as well. * * Source and destination must not be the same vector. */ template void vmult_add(OutVector &dst, const InVector &src) const; /** * Adding Matrix-vector multiplication. Add MT*src to * dst with M being this matrix. This function does the same * as vmult_add() but takes the transposed matrix. * * Note that while this function can operate on all vectors that offer * iterator classes, it is only really effective for objects of type * @ref Vector. * For all classes for which iterating over elements, or random member * access is expensive, this function is not efficient. In particular, if * you want to multiply with BlockVector objects, you should consider using * a BlockChunkSparseMatrix as well. * * Source and destination must not be the same vector. */ template void Tvmult_add(OutVector &dst, const InVector &src) const; /** * Return the square of the norm of the vector $v$ with respect to the norm * induced by this matrix, i.e. $\left(v,Mv\right)$. This is useful, e.g. in * the finite element context, where the $L_2$ norm of a function equals the * matrix norm with respect to the @ref GlossMassMatrix "mass matrix" of the vector representing * the nodal values of the finite element function. * * Obviously, the matrix needs to be quadratic for this operation, and for * the result to actually be a norm it also needs to be either real * symmetric or complex hermitian. * * The underlying template types of both this matrix and the given vector * should either both be real or complex-valued, but not mixed, for this * function to make sense. */ template somenumber matrix_norm_square(const Vector &v) const; /** * Compute the matrix scalar product $\left(u,Mv\right)$. */ template somenumber matrix_scalar_product(const Vector &u, const Vector &v) const; /** * Compute the residual of an equation Mx=b, where the residual is * defined to be r=b-Mx. Write the residual into dst. The * l2 norm of the residual vector is returned. * * Source x and destination dst must not be the same vector. */ template somenumber residual(Vector &dst, const Vector &x, const Vector &b) const; /** @} */ /** * @name Matrix norms */ /** @{ */ /** * Return the l1-norm of the matrix, that is $|M|_1=max_{all columns * j}\sum_{all rows i} |M_ij|$, (max. sum of columns). This is the natural * matrix norm that is compatible to the l1-norm for vectors, i.e. * $|Mv|_1\leq |M|_1 |v|_1$. (cf. Haemmerlin-Hoffmann : Numerische * Mathematik) */ real_type l1_norm() const; /** * Return the linfty-norm of the matrix, that is $|M|_infty=max_{all rows * i}\sum_{all columns j} |M_ij|$, (max. sum of rows). This is the natural * matrix norm that is compatible to the linfty-norm of vectors, i.e. * $|Mv|_infty \leq |M|_infty |v|_infty$. (cf. Haemmerlin-Hoffmann : * Numerische Mathematik) */ real_type linfty_norm() const; /** * Return the frobenius norm of the matrix, i.e. the square root of the sum * of squares of all entries in the matrix. */ real_type frobenius_norm() const; /** @} */ /** * @name Preconditioning methods */ /** @{ */ /** * Apply the Jacobi preconditioner, which multiplies every element of the * src vector by the inverse of the respective diagonal element and * multiplies the result with the relaxation factor omega. */ template void precondition_Jacobi(Vector &dst, const Vector &src, const number omega = 1.) const; /** * Apply SSOR preconditioning to src. */ template void precondition_SSOR(Vector &dst, const Vector &src, const number om = 1.) const; /** * Apply SOR preconditioning matrix to src. */ template void precondition_SOR(Vector &dst, const Vector &src, const number om = 1.) const; /** * Apply transpose SOR preconditioning matrix to src. */ template void precondition_TSOR(Vector &dst, const Vector &src, const number om = 1.) const; /** * Perform SSOR preconditioning in-place. Apply the preconditioner matrix * without copying to a second vector. omega is the relaxation * parameter. */ template void SSOR(Vector &v, const number omega = 1.) const; /** * Perform an SOR preconditioning in-place. omega is the * relaxation parameter. */ template void SOR(Vector &v, const number om = 1.) const; /** * Perform a transpose SOR preconditioning in-place. omega is the * relaxation parameter. */ template void TSOR(Vector &v, const number om = 1.) const; /** * Perform a permuted SOR preconditioning in-place. * * The standard SOR method is applied in the order prescribed by * permutation, that is, first the row permutation[0], * then permutation[1] and so on. For efficiency reasons, the * permutation as well as its inverse are required. * * omega is the relaxation parameter. */ template void PSOR(Vector &v, const std::vector &permutation, const std::vector &inverse_permutation, const number om = 1.) const; /** * Perform a transposed permuted SOR preconditioning in-place. * * The transposed SOR method is applied in the order prescribed by * permutation, that is, first the row permutation[m()-1], * then permutation[m()-2] and so on. For efficiency reasons, the * permutation as well as its inverse are required. * * omega is the relaxation parameter. */ template void TPSOR(Vector &v, const std::vector &permutation, const std::vector &inverse_permutation, const number om = 1.) const; /** * Do one SOR step on v. Performs a direct SOR step with right * hand side b. */ template void SOR_step(Vector &v, const Vector &b, const number om = 1.) const; /** * Do one adjoint SOR step on v. Performs a direct TSOR step with * right hand side b. */ template void TSOR_step(Vector &v, const Vector &b, const number om = 1.) const; /** * Do one SSOR step on v. Performs a direct SSOR step with right * hand side b by performing TSOR after SOR. */ template void SSOR_step(Vector &v, const Vector &b, const number om = 1.) const; /** @} */ /** * @name Iterators */ /** @{ */ /** * Iterator starting at first entry of the matrix. This is the version for * constant matrices. * * Note that due to the layout in ChunkSparseMatrix, iterating over matrix * entries is considerably slower than for a sparse matrix, as the iterator * is travels row-by-row, whereas data is stored in chunks of several rows * and columns. */ const_iterator begin() const; /** * Final iterator. This is the version for constant matrices. * * Note that due to the layout in ChunkSparseMatrix, iterating over matrix * entries is considerably slower than for a sparse matrix, as the iterator * is travels row-by-row, whereas data is stored in chunks of several rows * and columns. */ const_iterator end() const; /** * Iterator starting at the first entry of the matrix. This is the version * for non-constant matrices. * * Note that due to the layout in ChunkSparseMatrix, iterating over matrix * entries is considerably slower than for a sparse matrix, as the iterator * is travels row-by-row, whereas data is stored in chunks of several rows * and columns. */ iterator begin(); /** * Final iterator. This is the version for non-constant matrices. * * Note that due to the layout in ChunkSparseMatrix, iterating over matrix * entries is considerably slower than for a sparse matrix, as the iterator * is travels row-by-row, whereas data is stored in chunks of several rows * and columns. */ iterator end(); /** * Iterator starting at the first entry of row r. This is the * version for constant matrices. * * Note that if the given row is empty, i.e. does not contain any nonzero * entries, then the iterator returned by this function equals * end(r). Note also that the iterator may not be dereferenceable in * that case. * * Note that due to the layout in ChunkSparseMatrix, iterating over matrix * entries is considerably slower than for a sparse matrix, as the iterator * is travels row-by-row, whereas data is stored in chunks of several rows * and columns. */ const_iterator begin(const unsigned int r) const; /** * Final iterator of row r. It points to the first element past the * end of line @p r, or past the end of the entire sparsity pattern. This is * the version for constant matrices. * * Note that the end iterator is not necessarily dereferenceable. This is in * particular the case if it is the end iterator for the last row of a * matrix. * * Note that due to the layout in ChunkSparseMatrix, iterating over matrix * entries is considerably slower than for a sparse matrix, as the iterator * is travels row-by-row, whereas data is stored in chunks of several rows * and columns. */ const_iterator end(const unsigned int r) const; /** * Iterator starting at the first entry of row r. This is the * version for non-constant matrices. * * Note that if the given row is empty, i.e. does not contain any nonzero * entries, then the iterator returned by this function equals * end(r). Note also that the iterator may not be dereferenceable in * that case. * * Note that due to the layout in ChunkSparseMatrix, iterating over matrix * entries is considerably slower than for a sparse matrix, as the iterator * is travels row-by-row, whereas data is stored in chunks of several rows * and columns. */ iterator begin(const unsigned int r); /** * Final iterator of row r. It points to the first element past the * end of line @p r, or past the end of the entire sparsity pattern. This is * the version for non-constant matrices. * * Note that the end iterator is not necessarily dereferenceable. This is in * particular the case if it is the end iterator for the last row of a * matrix. * * Note that due to the layout in ChunkSparseMatrix, iterating over matrix * entries is considerably slower than for a sparse matrix, as the iterator * is travels row-by-row, whereas data is stored in chunks of several rows * and columns. */ iterator end(const unsigned int r); /** @} */ /** * @name Input/Output */ /** @{ */ /** * Print the matrix to the given stream, using the format (line,col) * value, i.e. one nonzero entry of the matrix per line. */ void print(std::ostream &out) const; /** * Print the matrix in the usual format, i.e., as a matrix and not as a list * of nonzero elements. For better readability, elements not in the matrix * are displayed as empty space, while matrix elements which are explicitly * set to zero are displayed as such. * * The parameters allow for a flexible setting of the output format: * @p precision and @p scientific are used to determine the number format, * where scientific = false means fixed point notation. A zero * entry for @p width makes the function compute a width, but it may be * changed to a positive value, if output is crude. * * Additionally, a character for an empty value may be specified in * @p zero_string, and a character to separate row entries can be set in * @p separator. * * Finally, the whole matrix can be multiplied with a common @p denominator * to produce more readable output, even integers. * * @attention This function may produce @em large amounts of output if * applied to a large matrix! */ void print_formatted(std::ostream &out, const unsigned int precision = 3, const bool scientific = true, const unsigned int width = 0, const char *zero_string = " ", const double denominator = 1., const char *separator = " ") const; /** * Print the actual pattern of the matrix. For each entry with an absolute * value larger than threshold, a '*' is printed, a ':' for every value * smaller and a '.' for every entry not allocated. */ void print_pattern(std::ostream &out, const double threshold = 0.) const; /** * Write the data of this object en bloc to a file. This is done in a binary * mode, so the output is neither readable by humans nor (probably) by other * computers using a different operating system or number format. * * The purpose of this function is that you can swap out matrices and * sparsity pattern if you are short of memory, want to communicate between * different programs, or allow objects to be persistent across different * runs of the program. */ void block_write(std::ostream &out) const; /** * Read data that has previously been written by block_write() from a file. * This is done using the inverse operations to the above function, so it is * reasonably fast because the bitstream is not interpreted except for a few * numbers up front. * * The object is resized on this operation, and all previous contents are * lost. Note, however, that no checks are performed whether new data and * the underlying ChunkSparsityPattern object fit together. It is your * responsibility to make sure that the sparsity pattern and the data to be * read match. * * A primitive form of error checking is performed which will recognize the * bluntest attempts to interpret some data as a matrix stored bitwise to a * file that wasn't actually created that way, but not more. */ void block_read(std::istream &in); /** @} */ /** * @addtogroup Exceptions * @{ */ /** * Exception */ DeclException2(ExcInvalidIndex, int, int, << "You are trying to access the matrix entry with index <" << arg1 << ',' << arg2 << ">, but this entry does not exist in the sparsity pattern " "of this matrix." "\n\n" "The most common cause for this problem is that you used " "a method to build the sparsity pattern that did not " "(completely) take into account all of the entries you " "will later try to write into. An example would be " "building a sparsity pattern that does not include " "the entries you will write into due to constraints " "on degrees of freedom such as hanging nodes or periodic " "boundary conditions. In such cases, building the " "sparsity pattern will succeed, but you will get errors " "such as the current one at one point or other when " "trying to write into the entries of the matrix."); /** * Exception */ DeclException0(ExcDifferentChunkSparsityPatterns); /** * Exception */ DeclException2(ExcIteratorRange, int, int, << "The iterators denote a range of " << arg1 << " elements, but the given number of rows was " << arg2); /** * Exception */ DeclExceptionMsg(ExcSourceEqualsDestination, "You are attempting an operation on two vectors that " "are the same object, but the operation requires that the " "two objects are in fact different."); /** @} */ private: /** * Pointer to the sparsity pattern used for this matrix. In order to * guarantee that it is not deleted while still in use, we subscribe to it * using the ObserverPointer class. */ ObserverPointer> cols; /** * Array of values for all the nonzero entries. The position of an * entry within the matrix, i.e., the row and column number for a * given value in this array can only be deduced using the sparsity * pattern. The same holds for the more common operation of finding * an entry by its coordinates. */ std::unique_ptr val; /** * Allocated size of #val. This can be larger than the actually used part if * the size of the matrix was reduced sometime in the past by associating a * sparsity pattern with a smaller size to this object, using the reinit() * function. */ size_type max_len; /** * Return the location of entry $(i,j)$ within the val array. */ size_type compute_location(const size_type i, const size_type j) const; // make all other sparse matrices friends template friend class ChunkSparseMatrix; // Also give access to internal details to the iterator/accessor classes. template friend class ChunkSparseMatrixIterators::Iterator; template friend class ChunkSparseMatrixIterators::Accessor; }; /** @} */ #ifndef DOXYGEN /*---------------------- Inline functions -----------------------------------*/ template inline typename ChunkSparseMatrix::size_type ChunkSparseMatrix::m() const { Assert(cols != nullptr, ExcNeedsSparsityPattern()); return cols->rows; } template inline typename ChunkSparseMatrix::size_type ChunkSparseMatrix::n() const { Assert(cols != nullptr, ExcNeedsSparsityPattern()); return cols->cols; } template inline const ChunkSparsityPattern & ChunkSparseMatrix::get_sparsity_pattern() const { Assert(cols != nullptr, ExcNeedsSparsityPattern()); return *cols; } template inline typename ChunkSparseMatrix::size_type ChunkSparseMatrix::compute_location(const size_type i, const size_type j) const { const size_type chunk_size = cols->get_chunk_size(); const size_type chunk_index = cols->sparsity_pattern(i / chunk_size, j / chunk_size); if (chunk_index == ChunkSparsityPattern::invalid_entry) return ChunkSparsityPattern::invalid_entry; else { return (chunk_index * chunk_size * chunk_size + (i % chunk_size) * chunk_size + (j % chunk_size)); } } template inline void ChunkSparseMatrix::set(const size_type i, const size_type j, const number value) { AssertIsFinite(value); Assert(cols != nullptr, ExcNeedsSparsityPattern()); // it is allowed to set elements of the matrix that are not part of the // sparsity pattern, if the value to which we set it is zero const size_type index = compute_location(i, j); Assert((index != SparsityPattern::invalid_entry) || (value == 0.), ExcInvalidIndex(i, j)); if (index != SparsityPattern::invalid_entry) val[index] = value; } template inline void ChunkSparseMatrix::add(const size_type i, const size_type j, const number value) { AssertIsFinite(value); Assert(cols != nullptr, ExcNeedsSparsityPattern()); if (std::abs(value) != 0.) { const size_type index = compute_location(i, j); Assert((index != ChunkSparsityPattern::invalid_entry), ExcInvalidIndex(i, j)); val[index] += value; } } template template inline void ChunkSparseMatrix::add(const size_type row, const size_type n_cols, const size_type *col_indices, const number2 *values, const bool /*elide_zero_values*/, const bool /*col_indices_are_sorted*/) { // TODO: could be done more efficiently... for (size_type col = 0; col < n_cols; ++col) add(row, col_indices[col], static_cast(values[col])); } template inline ChunkSparseMatrix & ChunkSparseMatrix::operator*=(const number factor) { Assert(cols != nullptr, ExcNeedsSparsityPattern()); Assert(val != nullptr, ExcNotInitialized()); const size_type chunk_size = cols->get_chunk_size(); // multiply all elements of the matrix with the given factor. this includes // the padding elements in chunks that overlap the boundaries of the actual // matrix -- but since multiplication with a number does not violate the // invariant of keeping these elements at zero nothing can happen number *val_ptr = val.get(); const number *const end_ptr = val.get() + cols->sparsity_pattern.n_nonzero_elements() * chunk_size * chunk_size; while (val_ptr != end_ptr) *val_ptr++ *= factor; return *this; } template inline ChunkSparseMatrix & ChunkSparseMatrix::operator/=(const number factor) { Assert(cols != nullptr, ExcNeedsSparsityPattern()); Assert(val != nullptr, ExcNotInitialized()); Assert(std::abs(factor) != 0, ExcDivideByZero()); const number factor_inv = 1. / factor; const size_type chunk_size = cols->get_chunk_size(); // multiply all elements of the matrix with the given factor. this includes // the padding elements in chunks that overlap the boundaries of the actual // matrix -- but since multiplication with a number does not violate the // invariant of keeping these elements at zero nothing can happen number *val_ptr = val.get(); const number *const end_ptr = val.get() + cols->sparsity_pattern.n_nonzero_elements() * chunk_size * chunk_size; while (val_ptr != end_ptr) *val_ptr++ *= factor_inv; return *this; } template inline number ChunkSparseMatrix::operator()(const size_type i, const size_type j) const { Assert(cols != nullptr, ExcNeedsSparsityPattern()); AssertThrow(compute_location(i, j) != SparsityPattern::invalid_entry, ExcInvalidIndex(i, j)); return val[compute_location(i, j)]; } template inline number ChunkSparseMatrix::el(const size_type i, const size_type j) const { Assert(cols != nullptr, ExcNeedsSparsityPattern()); const size_type index = compute_location(i, j); if (index != ChunkSparsityPattern::invalid_entry) return val[index]; else return 0; } template inline number ChunkSparseMatrix::diag_element(const size_type i) const { Assert(cols != nullptr, ExcNeedsSparsityPattern()); Assert(m() == n(), ExcNotQuadratic()); AssertIndexRange(i, m()); // Use that the first element in each row of a quadratic matrix is the main // diagonal of the chunk sparsity pattern const size_type chunk_size = cols->get_chunk_size(); return val[cols->sparsity_pattern.rowstart[i / chunk_size] * chunk_size * chunk_size + (i % chunk_size) * chunk_size + (i % chunk_size)]; } template template inline void ChunkSparseMatrix::copy_from(const ForwardIterator begin, const ForwardIterator end) { Assert(static_cast(std::distance(begin, end)) == m(), ExcIteratorRange(std::distance(begin, end), m())); // for use in the inner loop, we define an alias to the type of the inner // iterators using inner_iterator = typename std::iterator_traits::value_type::const_iterator; size_type row = 0; for (ForwardIterator i = begin; i != end; ++i, ++row) { const inner_iterator end_of_row = i->end(); for (inner_iterator j = i->begin(); j != end_of_row; ++j) // write entries set(row, j->first, j->second); } } //--------------------------------------------------------------------------- namespace ChunkSparseMatrixIterators { template inline Accessor::Accessor(const MatrixType *matrix, const unsigned int row) : ChunkSparsityPatternIterators::Accessor(&matrix->get_sparsity_pattern(), row) , matrix(matrix) {} template inline Accessor::Accessor(const MatrixType *matrix) : ChunkSparsityPatternIterators::Accessor(&matrix->get_sparsity_pattern()) , matrix(matrix) {} template inline Accessor::Accessor( const ChunkSparseMatrixIterators::Accessor &a) : ChunkSparsityPatternIterators::Accessor(a) , matrix(&a.get_matrix()) {} template inline number Accessor::value() const { const unsigned int chunk_size = matrix->get_sparsity_pattern().get_chunk_size(); return matrix->val[reduced_index() * chunk_size * chunk_size + chunk_row * chunk_size + chunk_col]; } template inline const typename Accessor::MatrixType & Accessor::get_matrix() const { return *matrix; } template inline Accessor::Reference::Reference(const Accessor *accessor, const bool) : accessor(accessor) {} template inline Accessor::Reference::operator number() const { const unsigned int chunk_size = accessor->matrix->get_sparsity_pattern().get_chunk_size(); return accessor->matrix ->val[accessor->reduced_index() * chunk_size * chunk_size + accessor->chunk_row * chunk_size + accessor->chunk_col]; } template inline const typename Accessor::Reference & Accessor::Reference::operator=(const number n) const { const unsigned int chunk_size = accessor->matrix->get_sparsity_pattern().get_chunk_size(); accessor->matrix ->val[accessor->reduced_index() * chunk_size * chunk_size + accessor->chunk_row * chunk_size + accessor->chunk_col] = n; return *this; } template inline const typename Accessor::Reference & Accessor::Reference::operator+=(const number n) const { const unsigned int chunk_size = accessor->matrix->get_sparsity_pattern().get_chunk_size(); accessor->matrix ->val[accessor->reduced_index() * chunk_size * chunk_size + accessor->chunk_row * chunk_size + accessor->chunk_col] += n; return *this; } template inline const typename Accessor::Reference & Accessor::Reference::operator-=(const number n) const { const unsigned int chunk_size = accessor->matrix->get_sparsity_pattern().get_chunk_size(); accessor->matrix ->val[accessor->reduced_index() * chunk_size * chunk_size + accessor->chunk_row * chunk_size + accessor->chunk_col] -= n; return *this; } template inline const typename Accessor::Reference & Accessor::Reference::operator*=(const number n) const { const unsigned int chunk_size = accessor->matrix->get_sparsity_pattern().get_chunk_size(); accessor->matrix ->val[accessor->reduced_index() * chunk_size * chunk_size + accessor->chunk_row * chunk_size + accessor->chunk_col] *= n; return *this; } template inline const typename Accessor::Reference & Accessor::Reference::operator/=(const number n) const { const unsigned int chunk_size = accessor->matrix->get_sparsity_pattern().get_chunk_size(); accessor->matrix ->val[accessor->reduced_index() * chunk_size * chunk_size + accessor->chunk_row * chunk_size + accessor->chunk_col] /= n; return *this; } template inline Accessor::Accessor(MatrixType *matrix, const unsigned int row) : ChunkSparsityPatternIterators::Accessor(&matrix->get_sparsity_pattern(), row) , matrix(matrix) {} template inline Accessor::Accessor(MatrixType *matrix) : ChunkSparsityPatternIterators::Accessor(&matrix->get_sparsity_pattern()) , matrix(matrix) {} template inline typename Accessor::Reference Accessor::value() const { return Reference(this, true); } template inline typename Accessor::MatrixType & Accessor::get_matrix() const { return *matrix; } template inline Iterator::Iterator(MatrixType *matrix, const unsigned int row) : accessor(matrix, row) {} template inline Iterator::Iterator(MatrixType *matrix) : accessor(matrix) {} template inline Iterator::Iterator( const ChunkSparseMatrixIterators::Iterator &i) : accessor(*i) {} template inline Iterator & Iterator::operator++() { accessor.advance(); return *this; } template inline Iterator Iterator::operator++(int) { const Iterator iter = *this; accessor.advance(); return iter; } template inline const Accessor & Iterator::operator*() const { return accessor; } template inline const Accessor * Iterator::operator->() const { return &accessor; } template inline bool Iterator::operator==(const Iterator &other) const { return (accessor == other.accessor); } template inline bool Iterator::operator!=(const Iterator &other) const { return !(*this == other); } template inline bool Iterator::operator<(const Iterator &other) const { Assert(&accessor.get_matrix() == &other.accessor.get_matrix(), ExcInternalError()); return (accessor < other.accessor); } template inline bool Iterator::operator>(const Iterator &other) const { return (other < *this); } template inline int Iterator::operator-(const Iterator &other) const { Assert(&accessor.get_matrix() == &other.accessor.get_matrix(), ExcInternalError()); // TODO: can be optimized int difference = 0; if (*this < other) { Iterator copy = *this; while (copy != other) { ++copy; --difference; } } else { Iterator copy = other; while (copy != *this) { ++copy; ++difference; } } return difference; } template inline Iterator Iterator::operator+(const unsigned int n) const { Iterator x = *this; for (unsigned int i = 0; i < n; ++i) ++x; return x; } } // namespace ChunkSparseMatrixIterators template inline typename ChunkSparseMatrix::const_iterator ChunkSparseMatrix::begin() const { return const_iterator(this, 0); } template inline typename ChunkSparseMatrix::const_iterator ChunkSparseMatrix::end() const { return const_iterator(this); } template inline typename ChunkSparseMatrix::iterator ChunkSparseMatrix::begin() { return iterator(this, 0); } template inline typename ChunkSparseMatrix::iterator ChunkSparseMatrix::end() { return iterator(this); } template inline typename ChunkSparseMatrix::const_iterator ChunkSparseMatrix::begin(const unsigned int r) const { AssertIndexRange(r, m()); return const_iterator(this, r); } template inline typename ChunkSparseMatrix::const_iterator ChunkSparseMatrix::end(const unsigned int r) const { AssertIndexRange(r, m()); return const_iterator(this, r + 1); } template inline typename ChunkSparseMatrix::iterator ChunkSparseMatrix::begin(const unsigned int r) { AssertIndexRange(r, m()); return iterator(this, r); } template inline typename ChunkSparseMatrix::iterator ChunkSparseMatrix::end(const unsigned int r) { AssertIndexRange(r, m()); return iterator(this, r + 1); } #endif // DOXYGEN DEAL_II_NAMESPACE_CLOSE #endif