42#ifndef TPETRA_CRSGRAPHTRANSPOSER_DEF_HPP
43#define TPETRA_CRSGRAPHTRANSPOSER_DEF_HPP
45#include "Tpetra_CrsGraph.hpp"
46#include "Tpetra_Export.hpp"
48#include "Tpetra_Details_makeColMap.hpp"
50#include "Teuchos_ParameterList.hpp"
51#include "Teuchos_TimeMonitor.hpp"
52#include "KokkosSparse_Utils.hpp"
53#include "KokkosKernels_Handle.hpp"
54#include "KokkosSparse_spadd.hpp"
59 typename LocalIndicesType,
60 typename GlobalIndicesType,
62 struct ConvertLocalToGlobalFunctor
64 ConvertLocalToGlobalFunctor(
65 const LocalIndicesType& colindsOrig_,
66 const GlobalIndicesType& colindsConverted_,
67 const ColMapType& colmap_) :
68 colindsOrig (colindsOrig_),
69 colindsConverted (colindsConverted_),
72 KOKKOS_INLINE_FUNCTION
void
73 operator() (
const GO i)
const
75 colindsConverted(i) = colmap.getGlobalElement(colindsOrig(i));
77 LocalIndicesType colindsOrig;
78 GlobalIndicesType colindsConverted;
82 template<
class LO,
class GO,
class LOView,
class GOView,
class LocalMap>
83 struct ConvertGlobalToLocalFunctor
85 ConvertGlobalToLocalFunctor(LOView& lids_,
const GOView& gids_,
const LocalMap localColMap_)
86 : lids(lids_), gids(gids_), localColMap(localColMap_)
89 KOKKOS_FUNCTION
void operator() (
const GO i)
const
91 lids(i) = localColMap.getLocalElement(gids(i));
96 const LocalMap localColMap;
100 template <
typename size_type,
typename ordinal_type,
101 typename ArowptrsT,
typename BrowptrsT,
typename CrowptrsT,
102 typename AcolindsT,
typename BcolindsT,
typename CcolindsT>
103 struct SortedNumericIndicesOnlyFunctor {
105 SortedNumericIndicesOnlyFunctor(
const ArowptrsT& Arowptrs_,
106 const BrowptrsT& Browptrs_,
107 const CrowptrsT& Crowptrs_,
108 const AcolindsT& Acolinds_,
109 const BcolindsT& Bcolinds_,
110 const CcolindsT& Ccolinds_)
111 : Arowptrs(Arowptrs_),
116 Ccolinds(Ccolinds_) {}
118 KOKKOS_INLINE_FUNCTION
void operator()(
const ordinal_type i)
const
120 const ordinal_type ORDINAL_MAX = Kokkos::ArithTraits<ordinal_type>::max();
125 size_type Arowstart = Arowptrs(i);
126 size_type Arowlen = Arowptrs(i + 1) - Arowstart;
127 size_type Browstart = Browptrs(i);
128 size_type Browlen = Browptrs(i + 1) - Browstart;
129 ordinal_type Acol = (Arowlen == 0) ? ORDINAL_MAX : Acolinds(Arowstart);
130 ordinal_type Bcol = (Browlen == 0) ? ORDINAL_MAX : Bcolinds(Browstart);
131 size_type Coffset = Crowptrs(i);
132 while (Acol != ORDINAL_MAX || Bcol != ORDINAL_MAX)
134 ordinal_type Ccol = (Acol < Bcol) ? Acol : Bcol;
141 Acol = Acolinds(Arowstart + ai);
149 Bcol = Bcolinds(Browstart + bi);
151 Ccolinds(Coffset) = Ccol;
156 const ArowptrsT Arowptrs;
157 const BrowptrsT Browptrs;
158 const CrowptrsT Crowptrs;
159 const AcolindsT Acolinds;
160 const BcolindsT Bcolinds;
164 template <
typename size_type,
typename ordinal_type,
165 typename ArowptrsT,
typename BrowptrsT,
typename CrowptrsT,
166 typename AcolindsT,
typename BcolindsT,
typename CcolindsT>
167 struct UnsortedNumericIndicesOnlyFunctor {
169 UnsortedNumericIndicesOnlyFunctor(
170 const ArowptrsT Arowptrs_,
const BrowptrsT Browptrs_,
const CrowptrsT Crowptrs_,
171 const AcolindsT Acolinds_,
const BcolindsT Bcolinds_, CcolindsT Ccolinds_,
172 const CcolindsT Apos_,
const CcolindsT Bpos_)
173 : Arowptrs(Arowptrs_),
182 KOKKOS_INLINE_FUNCTION
void operator()(
const ordinal_type i)
const {
183 size_type CrowStart = Crowptrs(i);
184 size_type ArowStart = Arowptrs(i);
185 size_type ArowEnd = Arowptrs(i + 1);
186 size_type BrowStart = Browptrs(i);
187 size_type BrowEnd = Browptrs(i + 1);
189 for (size_type j = ArowStart; j < ArowEnd; j++) {
190 Ccolinds(CrowStart + Apos(j)) = Acolinds(j);
193 for (size_type j = BrowStart; j < BrowEnd; j++) {
194 Ccolinds(CrowStart + Bpos(j)) = Bcolinds(j);
197 const ArowptrsT Arowptrs;
198 const BrowptrsT Browptrs;
199 const CrowptrsT Crowptrs;
200 const AcolindsT Acolinds;
201 const BcolindsT Bcolinds;
203 const CcolindsT Apos;
204 const CcolindsT Bpos;
208 template<
class LocalOrdinal,
213 const std::string& label)
214 : origGraph_ (origGraph), label_ (label)
217 template<
class LocalOrdinal,
220 Teuchos::RCP<CrsGraph<LocalOrdinal, GlobalOrdinal, Node> >
222 symmetrize (
const Teuchos::RCP<Teuchos::ParameterList> ¶ms)
225 using device_type =
typename Node::device_type;
226 using execution_space =
typename device_type::execution_space;
227 using range_type = Kokkos::RangePolicy<execution_space, size_t>;
229 using impl_scalar_type = ::Tpetra::Details::DefaultTypes::scalar_type;
230 using row_ptrs_array =
typename local_graph_device_type::row_map_type::non_const_type ;
231 using col_inds_array =
typename local_graph_device_type::entries_type::non_const_type;
233 using global_col_inds_array =
typename Kokkos::View<GlobalOrdinal*, device_type>;
235 auto graph = origGraph_;
236 auto domain_map = graph->getDomainMap();
237 auto range_map = graph->getRangeMap();
238 auto row_map = graph->getRowMap();
239 auto col_map = graph->getColMap();
240 RCP<const map_type> col_map_sym;
241 RCP<const Import<LocalOrdinal,GlobalOrdinal,Node> > importer;
243 TEUCHOS_ASSERT(domain_map->isSameAs(*range_map));
244 TEUCHOS_ASSERT(domain_map->isSameAs(*row_map));
247 RCP<crs_graph_type> graphT = createTranspose (params);
249 auto col_map_T = graphT->getColMap();
250 TEUCHOS_ASSERT(!col_map_T.is_null());
251 TEUCHOS_ASSERT(domain_map->isSameAs(*graphT->getDomainMap()));
253 bool graphSorted = graph->isSorted();
254 bool graphTSorted = graphT->isSorted();
255 bool sorted = graphSorted && graphTSorted;
256 bool matchingColMaps = col_map->isSameAs(*col_map_T);
258 auto lclGraph = graph->getLocalGraphDevice();
259 auto lclGraphT = graphT->getLocalGraphDevice();
261 using KKH_LO = KokkosKernels::Experimental::KokkosKernelsHandle<size_t, LocalOrdinal, impl_scalar_type,
262 typename Node::execution_space,
typename Node::memory_space,
typename Node::memory_space>;
263 using KKH_GO = KokkosKernels::Experimental::KokkosKernelsHandle<size_t, GlobalOrdinal, impl_scalar_type,
264 typename Node::execution_space,
typename Node::memory_space,
typename Node::memory_space>;
266 auto rowptrs = lclGraph.row_map;
267 auto rowptrsT = lclGraphT.row_map;
268 auto colinds = lclGraph.entries;
269 auto colindsT = lclGraphT.entries;
271 auto nrows = rowptrs.extent(0) - 1;
272 auto rowptrsSym = row_ptrs_array(Kokkos::ViewAllocateWithoutInitializing(
"row ptrs sym"), nrows + 1);
274 col_inds_array colindsSym;
276 if(!matchingColMaps) {
278 auto lclColmap = col_map->getLocalMap();
279 global_col_inds_array colindsConverted(Kokkos::ViewAllocateWithoutInitializing(
"colinds (converted)"), colinds.extent(0));
280 ConvertLocalToGlobalFunctor<GlobalOrdinal, col_inds_array, global_col_inds_array, local_map_type> convert(colinds, colindsConverted, lclColmap);
281 Kokkos::parallel_for(
"colInds (converted)", range_type(0, colinds.extent(0)), convert);
284 auto lclColmapT = col_map_T->getLocalMap();
285 global_col_inds_array colindsTConverted(Kokkos::ViewAllocateWithoutInitializing(
"colindsT (converted)"), colindsT.extent(0));
286 ConvertLocalToGlobalFunctor<GlobalOrdinal, col_inds_array, global_col_inds_array, local_map_type> convertT(colindsT, colindsTConverted, lclColmapT);
287 Kokkos::parallel_for(
"colIndsT (converted)", range_type(0, colindsT.extent(0)), convertT);
291 handle.create_spadd_handle(
false);
292 auto addHandle = handle.get_spadd_handle();
294 global_col_inds_array globalColindsSym;
296 KokkosSparse::Experimental::spadd_symbolic
297 (&handle, rowptrs, colindsConverted, rowptrsT, colindsTConverted, rowptrsSym);
298 globalColindsSym = global_col_inds_array(Kokkos::ViewAllocateWithoutInitializing(
"global colinds sym"), addHandle->get_c_nnz());
300 UnsortedNumericIndicesOnlyFunctor<
301 size_t, GlobalOrdinal,
302 typename row_ptrs_array::const_type,
typename row_ptrs_array::const_type, row_ptrs_array,
303 typename global_col_inds_array::const_type,
typename global_col_inds_array::const_type, global_col_inds_array>
304 unsortedNumeric(rowptrs, rowptrsT, rowptrsSym,
305 colindsConverted, colindsTConverted, globalColindsSym,
306 addHandle->get_a_pos(), addHandle->get_b_pos());
307 Kokkos::parallel_for(
"KokkosSparse::SpAdd:Numeric::InputNotSorted",
308 range_type(0, nrows), unsortedNumeric);
311 Tpetra::Details::makeColMap<LocalOrdinal, GlobalOrdinal, Node>
312 (col_map_sym, domain_map, globalColindsSym);
315 auto lclColmapSym = col_map_sym->getLocalMap();
316 colindsSym = col_inds_array(
"colindsSym", globalColindsSym.extent(0));
317 ConvertGlobalToLocalFunctor<LocalOrdinal, GlobalOrdinal, col_inds_array, global_col_inds_array, typename map_type::local_map_type> convertSym(colindsSym, globalColindsSym, lclColmapSym);
318 Kokkos::parallel_for(range_type(0, globalColindsSym.extent(0)), convertSym);
324 handle.create_spadd_handle(sorted);
325 auto addHandle = handle.get_spadd_handle();
327 KokkosSparse::Experimental::spadd_symbolic
328 (&handle, rowptrs, colinds, rowptrsT, colindsT, rowptrsSym);
329 colindsSym = col_inds_array(Kokkos::ViewAllocateWithoutInitializing(
"C colinds"), addHandle->get_c_nnz());
332 SortedNumericIndicesOnlyFunctor<
333 size_t, LocalOrdinal,
334 typename row_ptrs_array::const_type,
typename row_ptrs_array::const_type, row_ptrs_array,
335 typename col_inds_array::const_type,
typename col_inds_array::const_type, col_inds_array>
336 sortedNumeric(rowptrs, rowptrsT, rowptrsSym,
337 colinds, colindsT, colindsSym);
338 Kokkos::parallel_for(
"KokkosSparse::SpAdd:Numeric::InputSorted",
339 range_type(0, nrows), sortedNumeric);
342 UnsortedNumericIndicesOnlyFunctor<
343 size_t, LocalOrdinal,
344 typename row_ptrs_array::const_type,
typename row_ptrs_array::const_type, row_ptrs_array,
345 typename col_inds_array::const_type,
typename col_inds_array::const_type, col_inds_array>
346 unsortedNumeric(rowptrs, rowptrsT, rowptrsSym,
347 colinds, colindsT, colindsSym,
348 addHandle->get_a_pos(), addHandle->get_b_pos());
349 Kokkos::parallel_for(
"KokkosSparse::SpAdd:Numeric::InputNotSorted",
350 range_type(0, nrows), unsortedNumeric);
354 col_map_sym = col_map;
355 importer = graph->getImporter();
360 KokkosSparse::sort_crs_graph<execution_space, row_ptrs_array, col_inds_array>(rowptrsSym, colindsSym);
362 local_graph_device_type lclGraphSym = local_graph_device_type(colindsSym, rowptrsSym);
364 RCP<Teuchos::ParameterList> graphParams = Teuchos::null;
366 graphParams = rcp(
new Teuchos::ParameterList);
367 graphParams->set(
"sorted",
false);
380 template<
class LocalOrdinal,
383 Teuchos::RCP<CrsGraph<LocalOrdinal, GlobalOrdinal, Node> >
389 RCP<crs_graph_type> transGraphWithSharedRows = createTransposeLocal (params);
391#ifdef HAVE_TPETRA_MMM_TIMINGS
392 const std::string prefix = std::string (
"Tpetra ") + label_ +
": ";
393 using Teuchos::TimeMonitor;
394 TimeMonitor MM (*TimeMonitor::getNewTimer (prefix +
"Transpose TAFC"));
401 RCP<const export_type> exporter =
402 transGraphWithSharedRows->getExporter ();
403 if (exporter.is_null ()) {
404 return transGraphWithSharedRows;
407 Teuchos::ParameterList labelList;
408#ifdef HAVE_TPETRA_MMM_TIMINGS
409 labelList.set(
"Timer Label", label_);
411 if(! params.is_null ()) {
412 const char paramName[] =
"compute global constants";
413 labelList.set (paramName, params->get (paramName,
true));
418 return exportAndFillCompleteCrsGraph<crs_graph_type>
419 (transGraphWithSharedRows, *exporter, Teuchos::null,
420 Teuchos::null, Teuchos::rcpFromRef (labelList));
424 template<
class LocalOrdinal,
427 Teuchos::RCP<CrsGraph<LocalOrdinal, GlobalOrdinal, Node> >
433 using Teuchos::rcp_dynamic_cast;
434 using LO = LocalOrdinal;
435 using GO = GlobalOrdinal;
439#ifdef HAVE_TPETRA_MMM_TIMINGS
440 std::string prefix = std::string(
"Tpetra ") + label_ +
": ";
441 using Teuchos::TimeMonitor;
442 TimeMonitor MM (*TimeMonitor::getNewTimer (prefix +
"Transpose Local"));
445 const bool sort = [&] () {
446 constexpr bool sortDefault =
true;
447 const char sortParamName[] =
"sort";
448 return params.get () ==
nullptr ? sortDefault :
449 params->get (sortParamName, sortDefault);
453 local_graph_device_type lclGraph = origGraph_->getLocalGraphDevice ();
456 using c_rowmap_t =
typename local_graph_device_type::row_map_type;
457 using c_entries_t =
typename local_graph_device_type::entries_type;
458 using rowmap_t =
typename local_graph_device_type::row_map_type::non_const_type;
459 using entries_t =
typename local_graph_device_type::entries_type::non_const_type;
460 LocalOrdinal numCols = origGraph_->getColMap()->getLocalNumElements();
461 rowmap_t lclGraphT_rowmap(
"Transpose rowmap", numCols + 1);
462 entries_t lclGraphT_entries(
463 Kokkos::ViewAllocateWithoutInitializing(
"Transpose entries"), lclGraph.entries.extent(0));
464 KokkosSparse::Impl::transpose_graph<
465 c_rowmap_t, c_entries_t,
467 rowmap_t,
typename local_graph_device_type::execution_space>(
468 lclGraph.numRows(), numCols,
469 lclGraph.row_map, lclGraph.entries,
470 lclGraphT_rowmap, lclGraphT_entries);
473 KokkosSparse::sort_crs_graph<
474 typename local_graph_device_type::execution_space,
475 rowmap_t, entries_t>(
480 local_graph_device_type lclGraphT = local_graph_device_type(lclGraphT_entries, lclGraphT_rowmap);
484 const auto origExport = origGraph_->getExporter ();
485 RCP<const import_type> myImport = origExport.is_null () ?
486 Teuchos::null : rcp (
new import_type (*origExport));
487 const auto origImport = origGraph_->getImporter ();
488 RCP<const export_type> myExport = origImport.is_null () ?
489 Teuchos::null : rcp (
new export_type (*origImport));
491 RCP<Teuchos::ParameterList> graphParams = Teuchos::null;
493 graphParams = rcp(
new Teuchos::ParameterList);
494 graphParams->set(
"sorted",
false);
498 origGraph_->getColMap (),
499 origGraph_->getRowMap (),
500 origGraph_->getRangeMap (),
501 origGraph_->getDomainMap (),
502 myImport, myExport, graphParams));
511#define TPETRA_CRSGRAPHTRANSPOSER_INSTANT(LO,GO,NODE) \
512 template class CrsGraphTransposer< LO , GO , NODE >;
Declare and define the functions Tpetra::Details::computeOffsetsFromCounts and Tpetra::computeOffsets...
Declaration and definition of functions for sorting "short" arrays of keys and corresponding values.
CrsGraphTransposer(const Teuchos::RCP< const crs_graph_type > &origGraph, const std::string &label=std::string())
Constructor that takes the graph to transpose.
Teuchos::RCP< crs_graph_type > createTransposeLocal(const Teuchos::RCP< Teuchos::ParameterList > ¶ms=Teuchos::null)
Compute and return the transpose of the graph given to the constructor.
Teuchos::RCP< crs_graph_type > createTranspose(const Teuchos::RCP< Teuchos::ParameterList > ¶ms=Teuchos::null)
Compute and return the transpose of the graph given to the constructor.
Teuchos::RCP< crs_graph_type > symmetrize(const Teuchos::RCP< Teuchos::ParameterList > ¶ms=Teuchos::null)
Compute and return graph+graph^T of the graph given to the constructor.
A distributed graph accessed by rows (adjacency lists) and stored sparsely.
Kokkos::StaticCrsGraph< local_ordinal_type, Kokkos::LayoutLeft, device_type, void, size_t > local_graph_device_type
The type of the part of the sparse graph on each MPI process.
"Local" part of Map suitable for Kokkos kernels.
Communication plan for data redistribution from a (possibly) multiply-owned to a uniquely-owned distr...
Communication plan for data redistribution from a uniquely-owned to a (possibly) multiply-owned distr...
Namespace Tpetra contains the class and methods constituting the Tpetra library.
void sort(View &view, const size_t &size)
Convenience wrapper for std::sort for host-accessible views.