This helper class can be called on multiple threads to compute the sparsity pattern (or graph) of the sparse matrix resulting from the discretization. More...

#include <sparsity_pattern.h>

Inheritance diagram for libMesh::SparsityPattern::Build:

[legend]

Public Member Functions
	Build (const DofMap &dof_map_in, const CouplingMatrix dof_coupling_in, const std::set< GhostingFunctor > &coupling_functors_in, const bool implicit_neighbor_dofs_in, const bool need_full_sparsity_pattern_in, const bool calculate_constrained_in=false, const StaticCondensationDofMap *sc=nullptr)

	Build (const Build &)=default
	Special functions. More...

Build &	operator= (const Build &)=delete

	Build (Build &&)=default

Build &	operator= (Build &&)=delete

	~Build ()=default

	Build (Build &other, Threads::split)
	Splitting constructor, for use in multithreaded loops. More...

void	operator() (const ConstElemRange &range)
	Add entries from a range of elements to this object's sparsity pattern. More...

void	join (const Build &other)
	Combine the sparsity pattern in `other` with this object's sparsity pattern. More...

void	parallel_sync ()
	Send sparsity pattern data relevant to other processors to those processors, and receive and incorporate data relevant to us. More...

const SparsityPattern::Graph &	get_sparsity_pattern () const
	Rows of sparse matrix indices, indexed by the offset from the first DoF on this processor. More...

const SparsityPattern::NonlocalGraph &	get_nonlocal_pattern () const
	Rows of sparse matrix indices, mapped from global DoF number, which belong on other processors. More...

std::size_t	n_nonzeros () const
	The total number of nonzeros in the global matrix. More...

const std::vector< dof_id_type > &	get_n_nz () const
	The number of on-processor nonzeros in my portion of the global matrix. More...

const std::vector< dof_id_type > &	get_n_oz () const
	The number of off-processor nonzeros in my portion of the global matrix. More...

void	apply_extra_sparsity_object (SparsityPattern::AugmentSparsityPattern &asp)
	Let a user-provided AugmentSparsityPattern subclass modify our sparsity structure. More...

void	apply_extra_sparsity_function (void(func)(SparsityPattern::Graph &sparsity, std::vector< dof_id_type > &n_nz, std::vector< dof_id_type > &n_oz, void context), void *context)
	Let a user-provided function modify our sparsity structure. More...

void	clear_full_sparsity ()
	Clear the "full" details of our sparsity structure, leaving only the counts of non-zero entries. More...

const Parallel::Communicator &	comm () const

processor_id_type	n_processors () const

processor_id_type	processor_id () const

Protected Attributes
const Parallel::Communicator &	_communicator

Private Member Functions
void	handle_vi_vj (const std::vector< dof_id_type > &element_dofs_i, const std::vector< dof_id_type > &element_dofs_j)

void	sorted_connected_dofs (const Elem *elem, std::vector< dof_id_type > &dofs_vi, unsigned int vi)

Private Attributes
const DofMap &	dof_map

const CouplingMatrix *	dof_coupling

const std::set< GhostingFunctor * > &	coupling_functors

const bool	implicit_neighbor_dofs

const bool	need_full_sparsity_pattern

const bool	calculate_constrained

const StaticCondensationDofMap *const	sc

std::unordered_set< dof_id_type >	hashed_dof_sets
	If there are "spider" nodes in the mesh (i.e. More...

std::vector< dof_id_type >	dummy_vec
	A dummy work vector to avoid repeated memory allocations. More...

SparsityPattern::Graph	sparsity_pattern

SparsityPattern::NonlocalGraph	nonlocal_pattern

std::vector< dof_id_type >	n_nz

std::vector< dof_id_type >	n_oz

Detailed Description

This helper class can be called on multiple threads to compute the sparsity pattern (or graph) of the sparse matrix resulting from the discretization.

This pattern may be used directly by a particular sparse matrix format (e.g. LaspackMatrix) or indirectly (e.g. PetscMatrixBase). In the latter case the number of nonzeros per row of the matrix is needed for efficient preallocation. In this case it suffices to provide estimate (but bounding) values, and in this case the threaded method can take some short-cuts for efficiency.

Definition at line 103 of file sparsity_pattern.h.

Constructor & Destructor Documentation

◆ Build() [1/4]

libMesh::SparsityPattern::Build::Build	(	const DofMap &	dof_map_in,
		const CouplingMatrix *	dof_coupling_in,
		const std::set< GhostingFunctor *> &	coupling_functors_in,
		const bool	implicit_neighbor_dofs_in,
		const bool	need_full_sparsity_pattern_in,
		const bool	calculate_constrained_in = `false`,
		const StaticCondensationDofMap *	sc = `nullptr`
	)

Definition at line 47 of file sparsity_pattern.C.

                                                             :
   ParallelObject(dof_map_in),
   dof_map(dof_map_in),
   dof_coupling(dof_coupling_in),
   coupling_functors(coupling_functors_in),
   implicit_neighbor_dofs(implicit_neighbor_dofs_in),
   need_full_sparsity_pattern(need_full_sparsity_pattern_in),
   calculate_constrained(calculate_constrained_in),
   sc(sc_in),
   sparsity_pattern(),
   nonlocal_pattern(),
   n_nz(),
   n_oz()
 {}

◆ Build() [2/4]

libMesh::SparsityPattern::Build::Build ( const Build & )

default

Special functions.

The Build object holds references to DofMap and coupling functors, therefore it can't be assigned.

◆ Build() [3/4]

libMesh::SparsityPattern::Build::Build ( Build && )

default

◆ ~Build()

libMesh::SparsityPattern::Build::~Build ( )

default

◆ Build() [4/4]

libMesh::SparsityPattern::Build::Build	(	Build &	other,
		Threads::split
	)

Splitting constructor, for use in multithreaded loops.

Definition at line 70 of file sparsity_pattern.C.

                                          :
   ParallelObject(other),
   dof_map(other.dof_map),
   dof_coupling(other.dof_coupling),
   coupling_functors(other.coupling_functors),
   implicit_neighbor_dofs(other.implicit_neighbor_dofs),
   need_full_sparsity_pattern(other.need_full_sparsity_pattern),
   calculate_constrained(other.calculate_constrained),
   sc(other.sc),
   hashed_dof_sets(other.hashed_dof_sets),
   sparsity_pattern(),
   nonlocal_pattern(),
   n_nz(),
   n_oz()
 {}

Member Function Documentation

◆ apply_extra_sparsity_function()

void libMesh::SparsityPattern::Build::apply_extra_sparsity_function	(	void()(SparsityPattern::Graph &sparsity, std::vector< dof_id_type > &n_nz, std::vector< dof_id_type > &n_oz, void context)	func,
		void *	context
	)

inline

Let a user-provided function modify our sparsity structure.

Definition at line 191 of file sparsity_pattern.h.

References n_nz, n_oz, and sparsity_pattern.

196 { func(sparsity_pattern, n_nz, n_oz, context); }

libMesh::SparsityPattern::Build::sparsity_pattern

SparsityPattern::Graph sparsity_pattern

Definition: sparsity_pattern.h:244

libMesh::SparsityPattern::Build::n_nz

std::vector< dof_id_type > n_nz

Definition: sparsity_pattern.h:248

libMesh::SparsityPattern::Build::n_oz

std::vector< dof_id_type > n_oz

Definition: sparsity_pattern.h:250

◆ apply_extra_sparsity_object()

void libMesh::SparsityPattern::Build::apply_extra_sparsity_object ( SparsityPattern::AugmentSparsityPattern & asp )

Let a user-provided AugmentSparsityPattern subclass modify our sparsity structure.

Definition at line 578 of file sparsity_pattern.C.

References libMesh::SparsityPattern::AugmentSparsityPattern::augment_sparsity_pattern(), n_nz, n_oz, and sparsity_pattern.

 {
   asp.augment_sparsity_pattern (sparsity_pattern, n_nz, n_oz);
 }

◆ clear_full_sparsity()

void libMesh::SparsityPattern::Build::clear_full_sparsity ( )

inline

Clear the "full" details of our sparsity structure, leaving only the counts of non-zero entries.

Definition at line 202 of file sparsity_pattern.h.

References nonlocal_pattern, and sparsity_pattern.

   {
     sparsity_pattern.clear();
     nonlocal_pattern.clear();
   }

◆ comm()

const Parallel::Communicator& libMesh::ParallelObject::comm ( ) const

inlineinherited

Returns: A reference to the Parallel::Communicator object used by this mesh.

Definition at line 97 of file parallel_object.h.

References libMesh::ParallelObject::_communicator.

98 { return _communicator; }

libMesh::ParallelObject::_communicator

const Parallel::Communicator & _communicator

Definition: parallel_object.h:120

◆ get_n_nz()

const std::vector<dof_id_type>& libMesh::SparsityPattern::Build::get_n_nz ( ) const

inline

The number of on-processor nonzeros in my portion of the global matrix.

Definition at line 172 of file sparsity_pattern.h.

References n_nz.

Referenced by libMesh::StaticCondensation::init().

173 { return n_nz; }

libMesh::SparsityPattern::Build::n_nz

std::vector< dof_id_type > n_nz

Definition: sparsity_pattern.h:248

◆ get_n_oz()

const std::vector<dof_id_type>& libMesh::SparsityPattern::Build::get_n_oz ( ) const

inline

The number of off-processor nonzeros in my portion of the global matrix.

Definition at line 179 of file sparsity_pattern.h.

References n_oz.

Referenced by libMesh::StaticCondensation::init().

180 { return n_oz; }

libMesh::SparsityPattern::Build::n_oz

std::vector< dof_id_type > n_oz

Definition: sparsity_pattern.h:250

◆ get_nonlocal_pattern()

const SparsityPattern::NonlocalGraph& libMesh::SparsityPattern::Build::get_nonlocal_pattern ( ) const

inline

Rows of sparse matrix indices, mapped from global DoF number, which belong on other processors.

Stored here only temporarily until a parallel_sync() sends them where they belong.

Definition at line 160 of file sparsity_pattern.h.

References nonlocal_pattern.

161 { return nonlocal_pattern; }

libMesh::SparsityPattern::Build::nonlocal_pattern

SparsityPattern::NonlocalGraph nonlocal_pattern

Definition: sparsity_pattern.h:246

◆ get_sparsity_pattern()

const SparsityPattern::Graph& libMesh::SparsityPattern::Build::get_sparsity_pattern ( ) const

inline

Rows of sparse matrix indices, indexed by the offset from the first DoF on this processor.

Definition at line 152 of file sparsity_pattern.h.

References sparsity_pattern.

153 { return sparsity_pattern; }

libMesh::SparsityPattern::Build::sparsity_pattern

SparsityPattern::Graph sparsity_pattern

Definition: sparsity_pattern.h:244

◆ handle_vi_vj()

void libMesh::SparsityPattern::Build::handle_vi_vj	(	const std::vector< dof_id_type > &	element_dofs_i,
		const std::vector< dof_id_type > &	element_dofs_j
	)

private

Definition at line 152 of file sparsity_pattern.C.

References dof_map, libMesh::DofMapBase::end_dof(), libMesh::DofMapBase::first_dof(), hashed_dof_sets, libMesh::Utility::hashword(), libMesh::Utility::hashword2(), nonlocal_pattern, libMesh::ParallelObject::processor_id(), libMesh::SparsityPattern::sort_row(), and sparsity_pattern.

Referenced by operator()().

 {
   const unsigned int n_dofs_on_element_i =
     cast_int<unsigned int>(element_dofs_i.size());
 
   const processor_id_type proc_id     = dof_map.processor_id();
   const dof_id_type first_dof_on_proc = dof_map.first_dof(proc_id);
   const dof_id_type end_dof_on_proc   = dof_map.end_dof(proc_id);
 
   std::vector<dof_id_type>
     dofs_to_add;
 
   const unsigned int n_dofs_on_element_j =
     cast_int<unsigned int>(element_dofs_j.size());
 
   // It only makes sense to compute hashes and see if we can skip
   // doing work when there are a "large" amount of DOFs for a given
   // element. The cutoff for "large" is somewhat arbitrarily chosen
   // based on a test case with a spider node that resulted in O(10^3)
   // entries in element_dofs_i for O(10^3) elements. Making this
   // number larger will disable the hashing optimization in more
   // cases.
   bool dofs_seen = false;
   if (n_dofs_on_element_j > 0 && n_dofs_on_element_i > 256)
     {
       auto hash_i = Utility::hashword(element_dofs_i);
       auto hash_j = Utility::hashword(element_dofs_j);
       auto final_hash = Utility::hashword2(hash_i, hash_j);
       auto result = hashed_dof_sets.insert(final_hash);
       // if insert failed, we have already seen these dofs
       dofs_seen = !result.second;
     }
 
   // there might be 0 dofs for the other variable on the same element
   // (when subdomain variables do not overlap) and that's when we do
   // not do anything
   if (n_dofs_on_element_j > 0 && !dofs_seen)
     {
       for (unsigned int i=0; i<n_dofs_on_element_i; i++)
         {
           const dof_id_type ig = element_dofs_i[i];
 
           SparsityPattern::Row * row;
 
           // We save non-local row components for now so we can
           // communicate them to other processors later.
 
           if ((ig >= first_dof_on_proc) &&
               (ig <  end_dof_on_proc))
             {
               // This is what I mean
               // libmesh_assert_greater_equal ((ig - first_dof_on_proc), 0);
               // but do the test like this because ig and
               // first_dof_on_proc are unsigned ints
               libmesh_assert_greater_equal (ig, first_dof_on_proc);
               libmesh_assert_less (ig, (sparsity_pattern.size() +
                                         first_dof_on_proc));
 
               row = &sparsity_pattern[ig - first_dof_on_proc];
             }
           else
             {
               row = &nonlocal_pattern[ig];
             }
 
           // If the row is empty we will add *all*
           // the element j DOFs, so just do that.
           if (row->empty())
             {
               row->insert(row->end(),
                           element_dofs_j.begin(),
                           element_dofs_j.end());
             }
           else
             {
               // Build a list of the DOF indices not found in the
               // sparsity pattern
               dofs_to_add.clear();
 
               // Cache iterators.  Low will move forward, subsequent
               // searches will be on smaller ranges
               SparsityPattern::Row::iterator
                 low  = std::lower_bound
                 (row->begin(), row->end(), element_dofs_j.front()),
                 high = std::upper_bound
                 (low,          row->end(), element_dofs_j.back());
 
               for (unsigned int j=0; j<n_dofs_on_element_j; j++)
                 {
                   const dof_id_type jg = element_dofs_j[j];
 
                   // See if jg is in the sorted range
                   std::pair<SparsityPattern::Row::iterator,
                             SparsityPattern::Row::iterator>
                     pos = std::equal_range (low, high, jg);
 
                   // Must add jg if it wasn't found
                   if (pos.first == pos.second)
                     dofs_to_add.push_back(jg);
 
                   // pos.first is now a valid lower bound for any
                   // remaining element j DOFs. (That's why we sorted them.)
                   // Use it for the next search
                   low = pos.first;
                 }
 
               // Add to the sparsity pattern
               if (!dofs_to_add.empty())
                 {
                   const std::size_t old_size = row->size();
 
                   row->insert (row->end(),
                                dofs_to_add.begin(),
                                dofs_to_add.end());
 
                   SparsityPattern::sort_row
                     (row->begin(), row->begin()+old_size,
                      row->end());
                 }
             }
         } // End dofs-of-var-i loop
     } // End if-dofs-of-var-j
 }

◆ join()

void libMesh::SparsityPattern::Build::join ( const Build & other )

Combine the sparsity pattern in other with this object's sparsity pattern.

Useful in multithreaded loops.

Definition at line 367 of file sparsity_pattern.C.

References dof_map, libMesh::DofMapBase::end_dof(), hashed_dof_sets, libMesh::libmesh_assert(), libMesh::DofMap::n_local_dofs(), nonlocal_pattern, libMesh::ParallelObject::processor_id(), and sparsity_pattern.

 {
   libmesh_assert_equal_to (sparsity_pattern.size(), other.sparsity_pattern.size());
 
   for (dof_id_type r=0; r<dof_map.n_local_dofs(); r++)
     {
       // increment the number of on and off-processor nonzeros in this row
       // (note this will be an upper bound unless we need the full sparsity pattern)
       SparsityPattern::Row       & my_row    = sparsity_pattern[r];
       const SparsityPattern::Row & their_row = other.sparsity_pattern[r];
 
       // simple copy if I have no dofs
       if (my_row.empty())
         my_row = their_row;
 
       // otherwise add their DOFs to mine, resort, and re-unique the row
       else if (!their_row.empty()) // do nothing for the trivial case where
         {                          // their row is empty
           my_row.insert (my_row.end(),
                          their_row.begin(),
                          their_row.end());
 
           // We cannot use SparsityPattern::sort_row() here because it expects
           // the [begin,middle) [middle,end) to be non-overlapping.  This is not
           // necessarily the case here, so use std::sort()
           std::sort (my_row.begin(), my_row.end());
 
           my_row.erase(std::unique (my_row.begin(), my_row.end()), my_row.end());
         }
     }
 
   // Move nonlocal row information to ourselves; the other thread
   // won't need it in the map after that.
   for (const auto & p : other.nonlocal_pattern)
     {
 #ifndef NDEBUG
       const dof_id_type dof_id = p.first;
 
       processor_id_type dbg_proc_id = 0;
       while (dof_id >= dof_map.end_dof(dbg_proc_id))
         dbg_proc_id++;
       libmesh_assert (dbg_proc_id != this->processor_id());
 #endif
 
       const SparsityPattern::Row & their_row = p.second;
 
       // We should have no empty values in a map
       libmesh_assert (!their_row.empty());
 
       if (auto my_it = nonlocal_pattern.find(p.first);
           my_it == nonlocal_pattern.end())
         {
           //          nonlocal_pattern[it->first].swap(their_row);
           nonlocal_pattern[p.first] = their_row;
         }
       else
         {
           SparsityPattern::Row & my_row = my_it->second;
 
           my_row.insert (my_row.end(),
                          their_row.begin(),
                          their_row.end());
 
           // We cannot use SparsityPattern::sort_row() here because it expects
           // the [begin,middle) [middle,end) to be non-overlapping.  This is not
           // necessarily the case here, so use std::sort()
           std::sort (my_row.begin(), my_row.end());
 
           my_row.erase(std::unique (my_row.begin(), my_row.end()), my_row.end());
         }
     }
 
   // Combine the other thread's hashed_dof_sets with ours.
   hashed_dof_sets.insert(other.hashed_dof_sets.begin(),
                          other.hashed_dof_sets.end());
 }

◆ n_nonzeros()

std::size_t libMesh::SparsityPattern::Build::n_nonzeros ( ) const

The total number of nonzeros in the global matrix.

Definition at line 584 of file sparsity_pattern.C.

References libMesh::ParallelObject::comm(), n_nz, n_oz, and TIMPI::Communicator::sum().

 {
   // At some point I'll remember that "C++17" compilers don't always
   // come with complete C++17 standard libraries.
   // std::size_t total_nonzeros = std::reduce(n_nz.begin(), n_nz.end(), std::size_t(0));
   // total_nonzeros += std::reduce(n_oz.begin(), n_oz.end(), std::size_t(0));
 
   std::size_t total_nonzeros = 0;
   for (auto nnzi : n_nz)
     total_nonzeros += nnzi;
   for (auto nozi : n_oz)
     total_nonzeros += nozi;
 
   this->comm().sum(total_nonzeros);
   return total_nonzeros;
 }

◆ n_processors()

processor_id_type libMesh::ParallelObject::n_processors ( ) const

inlineinherited

Returns: The number of processors in the group.

Definition at line 103 of file parallel_object.h.

References libMesh::ParallelObject::_communicator, libMesh::libmesh_assert(), and TIMPI::Communicator::size().

   {
     processor_id_type returnval =
       cast_int<processor_id_type>(_communicator.size());
     libmesh_assert(returnval); // We never have an empty comm
     return returnval;
   }

◆ operator()()

void libMesh::SparsityPattern::Build::operator() ( const ConstElemRange & range )

Add entries from a range of elements to this object's sparsity pattern.

Definition at line 279 of file sparsity_pattern.C.

References libMesh::DofMap::coupling_functors_begin(), libMesh::DofMap::coupling_functors_end(), dof_map, handle_vi_vj(), libMesh::MeshTools::Generation::Private::idx(), libMesh::DofObject::invalid_processor_id, libMesh::DofMap::merge_ghost_functor_outputs(), libMesh::DofMap::n_local_dofs(), libMesh::DofMap::n_variables(), sorted_connected_dofs(), and sparsity_pattern.

 {
   // Compute the sparsity structure of the global matrix.  This can be
   // fed into a PetscMatrixBase to allocate exactly the number of nonzeros
   // necessary to store the matrix.  This algorithm should be linear
   // in the (# of elements)*(# nodes per element)
   sparsity_pattern.resize(dof_map.n_local_dofs());
 
   // Handle dof coupling specified by library and user coupling functors
   {
     const unsigned int n_var = dof_map.n_variables();
 
     std::vector<std::vector<dof_id_type> > element_dofs_i(n_var);
 
     std::vector<const Elem *> coupled_neighbors;
     for (const auto & elem : range)
       {
         // Make some fake element iterators defining a range
         // pointing to only this element.
         Elem * const * elempp = const_cast<Elem * const *>(&elem);
         Elem * const * elemend = elempp+1;
 
         const MeshBase::const_element_iterator fake_elem_it =
           MeshBase::const_element_iterator(elempp,
                                            elemend,
                                            Predicates::NotNull<Elem * const *>());
 
         const MeshBase::const_element_iterator fake_elem_end =
           MeshBase::const_element_iterator(elemend,
                                            elemend,
                                            Predicates::NotNull<Elem * const *>());
 
         GhostingFunctor::map_type elements_to_couple;
         DofMap::CouplingMatricesSet temporary_coupling_matrices;
 
         dof_map.merge_ghost_functor_outputs(elements_to_couple,
                                             temporary_coupling_matrices,
                                             dof_map.coupling_functors_begin(),
                                             dof_map.coupling_functors_end(),
                                             fake_elem_it,
                                             fake_elem_end,
                                             DofObject::invalid_processor_id);
         for (unsigned int vi=0; vi<n_var; vi++)
           this->sorted_connected_dofs(elem, element_dofs_i[vi], vi);
 
         for (unsigned int vi=0; vi<n_var; vi++)
           for (const auto & [partner, ghost_coupling] : elements_to_couple)
             {
               // Loop over coupling matrix row variables if we have a
               // coupling matrix, or all variables if not.
               if (ghost_coupling)
                 {
                   libmesh_assert_equal_to (ghost_coupling->size(), n_var);
                   ConstCouplingRow ccr(vi, *ghost_coupling);
 
                   for (const auto & idx : ccr)
                     {
                       if (partner == elem)
                         this->handle_vi_vj(element_dofs_i[vi], element_dofs_i[idx]);
                       else
                         {
                           std::vector<dof_id_type> partner_dofs;
                           this->sorted_connected_dofs(partner, partner_dofs, idx);
                           this->handle_vi_vj(element_dofs_i[vi], partner_dofs);
                         }
                     }
                 }
               else
                 {
                   for (unsigned int vj = 0; vj != n_var; ++vj)
                     {
                       if (partner == elem)
                         this->handle_vi_vj(element_dofs_i[vi], element_dofs_i[vj]);
                       else
                         {
                           std::vector<dof_id_type> partner_dofs;
                           this->sorted_connected_dofs(partner, partner_dofs, vj);
                           this->handle_vi_vj(element_dofs_i[vi], partner_dofs);
                         }
                     }
                 }
             } // End ghosted element loop
       } // End range element loop
   } // End ghosting functor section
 }

◆ operator=() [1/2]

Build& libMesh::SparsityPattern::Build::operator= ( const Build & )

delete

◆ operator=() [2/2]

Build& libMesh::SparsityPattern::Build::operator= ( Build && )

delete

◆ parallel_sync()

void libMesh::SparsityPattern::Build::parallel_sync ( )

Send sparsity pattern data relevant to other processors to those processors, and receive and incorporate data relevant to us.

Definition at line 446 of file sparsity_pattern.C.

References libMesh::ParallelObject::comm(), dof_map, libMesh::DofMapBase::end_dof(), libMesh::DofMapBase::first_dof(), libMesh::libmesh_assert(), libMesh::DofMap::local_index(), libMesh::DofMap::n_local_dofs(), n_nz, n_oz, need_full_sparsity_pattern, nonlocal_pattern, and sparsity_pattern.

 {
   parallel_object_only();
   libmesh_assert(this->comm().verify(need_full_sparsity_pattern));
 
   const auto n_dofs_on_proc  = dof_map.n_local_dofs();
   const auto local_first_dof = dof_map.first_dof();
 
   // The data to send
   std::map<processor_id_type, std::vector<dof_id_type>> ids_to_send;
   std::map<processor_id_type, std::vector<Row>> rows_to_send;
 
   // Loop over the nonlocal rows and transform them into the new datastructure
   NonlocalGraph::iterator it = nonlocal_pattern.begin();
   while (it != nonlocal_pattern.end())
   {
     const auto dof_id = it->first;
     auto & row = it->second;
 
     processor_id_type proc_id = 0;
     while (dof_id >= dof_map.end_dof(proc_id))
       proc_id++;
 
     ids_to_send[proc_id].push_back(dof_id);
 
     // Note this invalidates the data in nonlocal_pattern
     rows_to_send[proc_id].push_back(std::move(row));
 
     // Might as well remove it since it's invalidated anyway
     it = nonlocal_pattern.erase(it);
   }
 
   std::map<processor_id_type, std::vector<dof_id_type>> received_ids_map;
 
   auto ids_action_functor =
     [& received_ids_map]
     (processor_id_type pid,
      const std::vector<dof_id_type> & received_ids)
     {
       received_ids_map.emplace(pid, received_ids);
     };
 
   Parallel::push_parallel_vector_data(this->comm(), ids_to_send,
                                       ids_action_functor);
 
   auto rows_action_functor =
     [this,
      & received_ids_map,
      local_first_dof]
     (processor_id_type pid,
      const std::vector<Row> & received_rows)
     {
       const std::vector<dof_id_type> & received_ids = libmesh_map_find(received_ids_map, pid);
 
       std::size_t n_rows = received_rows.size();
       libmesh_assert_equal_to(n_rows, received_ids.size());
 
       for (auto i : IntRange<std::size_t>(0, n_rows))
         {
           const auto r = received_ids[i];
           libmesh_assert(dof_map.local_index(r));
 
           const auto my_r = r - local_first_dof;
 
           auto & their_row = received_rows[i];
 
           auto & my_row = sparsity_pattern[my_r];
 
           // They wouldn't have sent an empty row
           libmesh_assert(!their_row.empty());
 
           // We can end up with an empty row on a dof that touches our
           // inactive elements but not our active ones
           if (my_row.empty())
             {
               my_row.assign (their_row.begin(), their_row.end());
             }
           else
             {
               my_row.insert (my_row.end(),
                              their_row.begin(),
                              their_row.end());
 
               // We cannot use SparsityPattern::sort_row() here because it expects
               // the [begin,middle) [middle,end) to be non-overlapping.  This is not
               // necessarily the case here, so use std::sort()
               std::sort (my_row.begin(), my_row.end());
 
               my_row.erase(std::unique (my_row.begin(), my_row.end()), my_row.end());
             }
 
         }
     };
 
   Parallel::push_parallel_vector_data(this->comm(), rows_to_send,
                                       rows_action_functor);
 
   // We should have sent everything at this point.
   libmesh_assert (nonlocal_pattern.empty());
 
   // assert these are empty because std::vector::resize will only append the specified element value
   // if the new size is greater than the current size. Elements whose indices are less than the
   // current size are untouched
   libmesh_assert(n_nz.empty());
   libmesh_assert(n_oz.empty());
   n_nz.resize (n_dofs_on_proc, 0);
   n_oz.resize (n_dofs_on_proc, 0);
 
   const dof_id_type first_dof_on_proc = dof_map.first_dof();
   const dof_id_type end_dof_on_proc   = dof_map.end_dof();
 
   for (dof_id_type i=0; i<n_dofs_on_proc; i++)
     {
       // Get the row of the sparsity pattern
       SparsityPattern::Row & row = sparsity_pattern[i];
 
       for (const auto & df : row)
         if ((df < first_dof_on_proc) || (df >= end_dof_on_proc))
           n_oz[i]++;
         else
           n_nz[i]++;
 
       libmesh_assert(n_nz[i] <= n_dofs_on_proc);
 
       // If we're not building a full sparsity pattern, then we want
       // to avoid overcounting these entries as much as possible.
       if (!need_full_sparsity_pattern)
         row.clear();
     }
 }

◆ processor_id()

processor_id_type libMesh::ParallelObject::processor_id ( ) const

inlineinherited

Returns: The rank of this processor in the group.

Definition at line 114 of file parallel_object.h.

References libMesh::ParallelObject::_communicator, and TIMPI::Communicator::rank().

115 { return cast_int<processor_id_type>(_communicator.rank()); }

TIMPI::Communicator::rank

processor_id_type rank() const

libMesh::ParallelObject::_communicator

const Parallel::Communicator & _communicator

Definition: parallel_object.h:120

◆ sorted_connected_dofs()

void libMesh::SparsityPattern::Build::sorted_connected_dofs	(	const Elem *	elem,
		std::vector< dof_id_type > &	dofs_vi,
		unsigned int	vi
	)

private

Definition at line 96 of file sparsity_pattern.C.

References libMesh::DofMap::dof_indices(), dof_map, dummy_vec, libMesh::DofMap::find_connected_dofs(), libMesh::invalid_uint, libMesh::Elem::p_level(), sc, and libMesh::StaticCondensationDofMap::uncondensed_vars().

Referenced by operator()().

 {
   if (this->sc)
   {
     // We build a sparsity pattern that will match the size of the condensed system. This is so that
     // we have the data necessary to init the reduced system matrix
     dofs_vi.clear();
 
     auto total_and_uncondensed_from_scalar_dofs_functor =
         [&dofs_vi](const Elem & /*elem*/,
                    std::vector<dof_id_type> & dof_indices,
                    const std::vector<dof_id_type> & scalar_dof_indices)
     {
       dof_indices.insert(dof_indices.end(), scalar_dof_indices.begin(), scalar_dof_indices.end());
       dofs_vi.insert(dofs_vi.end(), scalar_dof_indices.begin(), scalar_dof_indices.end());
     };
 
     auto total_and_uncondensed_from_field_dofs_functor =
         [&dofs_vi, this](const Elem & functor_elem,
                         const unsigned int node_num,
                         const unsigned int var_num,
                         std::vector<dof_id_type> & dof_indices,
                         const dof_id_type field_dof)
     {
       dof_indices.push_back(field_dof);
       if (this->sc->uncondensed_vars().count(var_num) ||
           (node_num != invalid_uint && !functor_elem.is_internal(node_num)))
         dofs_vi.push_back(field_dof);
     };
 
     dof_map.dof_indices(elem,
                         dummy_vec,
                         vi,
                         total_and_uncondensed_from_scalar_dofs_functor,
                         total_and_uncondensed_from_field_dofs_functor,
                         elem->p_level());
   }
   else
     dof_map.dof_indices (elem, dofs_vi, vi);
 
 #ifdef LIBMESH_ENABLE_CONSTRAINTS
   dof_map.find_connected_dofs (dofs_vi);
 #endif
   // We can be more efficient if we sort the element DOFs into
   // increasing order
   std::sort(dofs_vi.begin(), dofs_vi.end());
 
   // Handle cases where duplicate nodes are intentionally assigned to
   // a single element.
   dofs_vi.erase(std::unique(dofs_vi.begin(), dofs_vi.end()), dofs_vi.end());
 }

Member Data Documentation

◆ _communicator

const Parallel::Communicator& libMesh::ParallelObject::_communicator

protectedinherited

Definition at line 120 of file parallel_object.h.

Referenced by libMesh::EquationSystems::build_parallel_elemental_solution_vector(), libMesh::EquationSystems::build_parallel_solution_vector(), libMesh::StaticCondensation::close(), libMesh::ParallelObject::comm(), libMesh::CondensedEigenSystem::initialize_condensed_matrices(), libMesh::ParallelObject::n_processors(), libMesh::ParallelObject::operator=(), libMesh::ParallelObject::processor_id(), libMesh::BoundaryInfo::regenerate_id_sets(), and libMesh::StaticCondensationDofMap::reinit().

◆ calculate_constrained

const bool libMesh::SparsityPattern::Build::calculate_constrained

private

Definition at line 214 of file sparsity_pattern.h.

◆ coupling_functors

const std::set<GhostingFunctor *>& libMesh::SparsityPattern::Build::coupling_functors

private

Definition at line 211 of file sparsity_pattern.h.

◆ dof_coupling

const CouplingMatrix* libMesh::SparsityPattern::Build::dof_coupling

private

Definition at line 210 of file sparsity_pattern.h.

◆ dof_map

const DofMap& libMesh::SparsityPattern::Build::dof_map

private

Definition at line 209 of file sparsity_pattern.h.

Referenced by handle_vi_vj(), join(), operator()(), parallel_sync(), and sorted_connected_dofs().

◆ dummy_vec

std::vector<dof_id_type> libMesh::SparsityPattern::Build::dummy_vec

private

A dummy work vector to avoid repeated memory allocations.

Definition at line 231 of file sparsity_pattern.h.

Referenced by sorted_connected_dofs().

◆ hashed_dof_sets

std::unordered_set<dof_id_type> libMesh::SparsityPattern::Build::hashed_dof_sets

private

If there are "spider" nodes in the mesh (i.e.

a single node which is connected to many 1D elements) and Constraints, we can end up sorting the same set of DOFs multiple times in handle_vi_vj(), only to find that it has no net effect on the final sparsity. In such cases it is much faster to keep track of (element_dofs_i, element_dofs_j) pairs which have already been handled and not repeat the computation. We use this data structure to keep track of hashes of sets of dofs we have already seen, thus avoiding unnecessary calculations.

Definition at line 228 of file sparsity_pattern.h.

Referenced by handle_vi_vj(), and join().

◆ implicit_neighbor_dofs

const bool libMesh::SparsityPattern::Build::implicit_neighbor_dofs

private

Definition at line 212 of file sparsity_pattern.h.

◆ n_nz

std::vector<dof_id_type> libMesh::SparsityPattern::Build::n_nz

private

Definition at line 248 of file sparsity_pattern.h.

Referenced by apply_extra_sparsity_function(), apply_extra_sparsity_object(), get_n_nz(), n_nonzeros(), and parallel_sync().

◆ n_oz

std::vector<dof_id_type> libMesh::SparsityPattern::Build::n_oz

private

Definition at line 250 of file sparsity_pattern.h.

Referenced by apply_extra_sparsity_function(), apply_extra_sparsity_object(), get_n_oz(), n_nonzeros(), and parallel_sync().

◆ need_full_sparsity_pattern

const bool libMesh::SparsityPattern::Build::need_full_sparsity_pattern

private

Definition at line 213 of file sparsity_pattern.h.

Referenced by parallel_sync().

◆ nonlocal_pattern

SparsityPattern::NonlocalGraph libMesh::SparsityPattern::Build::nonlocal_pattern

private

Definition at line 246 of file sparsity_pattern.h.

Referenced by clear_full_sparsity(), get_nonlocal_pattern(), handle_vi_vj(), join(), and parallel_sync().

◆ sc

const StaticCondensationDofMap* const libMesh::SparsityPattern::Build::sc

private

Definition at line 215 of file sparsity_pattern.h.

Referenced by sorted_connected_dofs().

◆ sparsity_pattern

SparsityPattern::Graph libMesh::SparsityPattern::Build::sparsity_pattern

private

Definition at line 244 of file sparsity_pattern.h.

Referenced by apply_extra_sparsity_function(), apply_extra_sparsity_object(), clear_full_sparsity(), get_sparsity_pattern(), handle_vi_vj(), join(), operator()(), and parallel_sync().

The documentation for this class was generated from the following files:

include/base/sparsity_pattern.h
src/base/sparsity_pattern.C

Public Member Functions

Protected Attributes

Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

◆ Build() [1/4]

◆ Build() [2/4]

◆ Build() [3/4]

◆ ~Build()

◆ Build() [4/4]

Member Function Documentation

◆ apply_extra_sparsity_function()

◆ apply_extra_sparsity_object()

◆ clear_full_sparsity()

◆ comm()

◆ get_n_nz()

◆ get_n_oz()

◆ get_nonlocal_pattern()

◆ get_sparsity_pattern()

◆ handle_vi_vj()

◆ join()

◆ n_nonzeros()

◆ n_processors()

◆ operator()()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ parallel_sync()

◆ processor_id()

◆ sorted_connected_dofs()

Member Data Documentation

◆ _communicator

◆ calculate_constrained

◆ coupling_functors

◆ dof_coupling

◆ dof_map

◆ dummy_vec

◆ hashed_dof_sets

◆ implicit_neighbor_dofs

◆ n_nz

◆ n_oz

◆ need_full_sparsity_pattern

◆ nonlocal_pattern

◆ sc

◆ sparsity_pattern