DOLFIN
DOLFIN C++ interface
SparsityPattern.h
1 // Copyright (C) 2007-2011 Garth N. Wells
2 //
3 // This file is part of DOLFIN.
4 //
5 // DOLFIN is free software: you can redistribute it and/or modify
6 // it under the terms of the GNU Lesser General Public License as published by
7 // the Free Software Foundation, either version 3 of the License, or
8 // (at your option) any later version.
9 //
10 // DOLFIN is distributed in the hope that it will be useful,
11 // but WITHOUT ANY WARRANTY; without even the implied warranty of
12 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 // GNU Lesser General Public License for more details.
14 //
15 // You should have received a copy of the GNU Lesser General Public License
16 // along with DOLFIN. If not, see <http://www.gnu.org/licenses/>.
17 //
18 // Modified by Anders Logg, 2007-2009.
19 //
20 // First added: 2007-03-13
21 // Last changed: 2011-01-02
22 
23 #ifndef __SPARSITY_PATTERN_H
24 #define __SPARSITY_PATTERN_H
25 
26 #include <memory>
27 #include <string>
28 #include <unordered_map>
29 #include <utility>
30 #include <vector>
31 
32 #include <dolfin/common/ArrayView.h>
33 #include <dolfin/common/MPI.h>
34 #include <dolfin/common/Set.h>
35 #include <dolfin/common/types.h>
36 
37 namespace dolfin
38 {
39 
40  class IndexMap;
41 
44 
46  {
47 
48  // NOTE: Do not change this typedef without performing careful
49  // performance profiling
52 
53  public:
54 
56  enum class Type {sorted, unsorted};
57 
59  SparsityPattern(MPI_Comm comm, std::size_t primary_dim);
60 
62  SparsityPattern(MPI_Comm comm,
63  std::vector<std::shared_ptr<const IndexMap>> index_maps,
64  std::size_t primary_dim);
65 
67  void init(std::vector<std::shared_ptr<const IndexMap>> index_maps);
68 
71 
73  void insert_global(const std::vector<
75 
77  void insert_local(const std::vector<
79 
83  const std::vector<ArrayView<const dolfin::la_index>>& entries);
84 
89  void insert_full_rows_local(const std::vector<std::size_t>& rows);
90 
92  std::size_t rank() const;
93 
96  std::size_t primary_dim() const
97  { return _primary_dim; }
98 
100  std::pair<std::size_t, std::size_t> local_range(std::size_t dim) const;
101 
103  std::size_t num_nonzeros() const;
104 
108  void num_nonzeros_diagonal(std::vector<std::size_t>& num_nonzeros) const;
109 
115  void
116  num_nonzeros_off_diagonal(std::vector<std::size_t>& num_nonzeros) const;
117 
120  void num_local_nonzeros(std::vector<std::size_t>& num_nonzeros) const;
121 
123  void apply();
124 
126  MPI_Comm mpi_comm() const
127  { return _mpi_comm.comm(); }
128 
130  std::string str(bool verbose) const;
131 
134  std::vector<std::vector<std::size_t>> diagonal_pattern(Type type) const;
135 
139  std::vector<std::vector<std::size_t>> off_diagonal_pattern(Type type) const;
140 
141  private:
142 
143  // Other insertion methods will call this method providing the
144  // appropriate mapping of the indices in the entries.
145  //
146  // The primary dim entries must be local
147  // The primary_codim entries must be global
148  void insert_entries(
149  const std::vector<ArrayView<const dolfin::la_index>>& entries,
150  const std::function<dolfin::la_index(const dolfin::la_index, const IndexMap&)>& primary_dim_map,
151  const std::function<dolfin::la_index(const dolfin::la_index, const IndexMap&)>& primary_codim_map);
152 
153  // Print some useful information
154  void info_statistics() const;
155 
156  // Primary sparsity pattern storage dimension (e.g., 0=row
157  // partition, 1=column partition)
158  const std::size_t _primary_dim;
159 
160  // MPI communicator
161  dolfin::MPI::Comm _mpi_comm;
162 
163  // IndexMaps for each dimension
164  std::vector<std::shared_ptr<const IndexMap>> _index_maps;
165 
166  // Sparsity patterns for diagonal and off-diagonal blocks
167  std::vector<set_type> diagonal;
168  std::vector<set_type> off_diagonal;
169 
170  // List of full rows (or columns, according to primary dimension).
171  // Full rows are kept separately to circumvent quadratic scaling
172  // (caused by linear insertion time into dolfin::Set; std::set has
173  // logarithmic insertion, which would result in N log(N) overall
174  // complexity for dense rows)
175  set_type full_rows;
176 
177  // Sparsity pattern for non-local entries stored as [i0, j0, i1, j1, ...]
178  std::vector<std::size_t> non_local;
179 
180  };
181 
182 }
183 #endif
dolfin::SparsityPattern::Type
Type
Whether SparsityPattern is sorted.
Definition: SparsityPattern.h:56
dolfin::SparsityPattern::num_nonzeros_off_diagonal
void num_nonzeros_off_diagonal(std::vector< std::size_t > &num_nonzeros) const
Definition: SparsityPattern.cpp:327
dolfin::SparsityPattern::init
void init(std::vector< std::shared_ptr< const IndexMap >> index_maps)
Initialize sparsity pattern for a generic tensor.
Definition: SparsityPattern.cpp:49
dolfin::Set< std::size_t >
dolfin::ArrayView
Definition: ArrayView.h:32
dolfin::MPI::Comm::comm
MPI_Comm comm() const
Return the underlying MPI_Comm object.
Definition: MPI.cpp:117
dolfin::SparsityPattern::insert_local
void insert_local(const std::vector< ArrayView< const dolfin::la_index >> &entries)
Insert non-zero entries using local (process-wise) indices.
Definition: SparsityPattern.cpp:130
dolfin::IndexMap
Definition: IndexMap.h:36
dolfin::SparsityPattern::mpi_comm
MPI_Comm mpi_comm() const
Return MPI communicator.
Definition: SparsityPattern.h:126
dolfin::SparsityPattern::num_local_nonzeros
void num_local_nonzeros(std::vector< std::size_t > &num_nonzeros) const
Definition: SparsityPattern.cpp:355
dolfin::SparsityPattern::apply
void apply()
Finalize sparsity pattern.
Definition: SparsityPattern.cpp:368
dolfin::SparsityPattern::off_diagonal_pattern
std::vector< std::vector< std::size_t > > off_diagonal_pattern(Type type) const
Definition: SparsityPattern.cpp:545
dolfin::SparsityPattern::num_nonzeros_diagonal
void num_nonzeros_diagonal(std::vector< std::size_t > &num_nonzeros) const
Definition: SparsityPattern.cpp:305
dolfin::la_index
PetscInt la_index
Index type for compatibility with linear algebra backend(s)
Definition: types.h:32
dolfin::SparsityPattern
Definition: SparsityPattern.h:46
dolfin::SparsityPattern::num_nonzeros
std::size_t num_nonzeros() const
Return number of local nonzeros.
Definition: SparsityPattern.cpp:283
dolfin::SparsityPattern::diagonal_pattern
std::vector< std::vector< std::size_t > > diagonal_pattern(Type type) const
Definition: SparsityPattern.cpp:512
dolfin::SparsityPattern::insert_full_rows_local
void insert_full_rows_local(const std::vector< std::size_t > &rows)
Definition: SparsityPattern.cpp:258
dolfin::SparsityPattern::insert_local_global
void insert_local_global(const std::vector< ArrayView< const dolfin::la_index >> &entries)
Definition: SparsityPattern.cpp:149
dolfin::SparsityPattern::str
std::string str(bool verbose) const
Return informal string representation (pretty-print)
Definition: SparsityPattern.cpp:485
dolfin::SparsityPattern::local_range
std::pair< std::size_t, std::size_t > local_range(std::size_t dim) const
Return local range for dimension dim.
Definition: SparsityPattern.cpp:277
dolfin::SparsityPattern::rank
std::size_t rank() const
Return rank.
Definition: SparsityPattern.cpp:271
dolfin::SparsityPattern::insert_global
void insert_global(dolfin::la_index i, dolfin::la_index j)
Insert a global entry - will be fixed by apply()
Definition: SparsityPattern.cpp:99
dolfin::SparsityPattern::SparsityPattern
SparsityPattern(MPI_Comm comm, std::size_t primary_dim)
Create empty sparsity pattern.
Definition: SparsityPattern.cpp:35
dolfin::SparsityPattern::primary_dim
std::size_t primary_dim() const
Definition: SparsityPattern.h:96
dolfin::MPI::Comm
Definition: MPI.h:77
dolfin
Definition: adapt.h:30