Tpetra Matrix/Vector Services: Tpetra_CrsGraph

00001 //@HEADER
00002 // ************************************************************************
00003 // 
00004 //               Tpetra: Templated Linear Algebra Services Package 
00005 //                 Copyright (2008) Sandia Corporation
00006 // 
00007 // Under terms of Contract DE-AC04-94AL85000, there is a non-exclusive
00008 // license for use of this work by or on behalf of the U.S. Government.
00009 // 
00010 // This library is free software; you can redistribute it and/or modify
00011 // it under the terms of the GNU Lesser General Public License as
00012 // published by the Free Software Foundation; either version 2.1 of the
00013 // License, or (at your option) any later version.
00014 //  
00015 // This library is distributed in the hope that it will be useful, but
00016 // WITHOUT ANY WARRANTY; without even the implied warranty of
00017 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00018 // Lesser General Public License for more details.
00019 //  
00020 // You should have received a copy of the GNU Lesser General Public
00021 // License along with this library; if not, write to the Free Software
00022 // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
00023 // USA
00024 // Questions? Contact Michael A. Heroux (maherou@sandia.gov) 
00025 // 
00026 // ************************************************************************
00027 //@HEADER
00028 
00029 #ifndef TPETRA_CRSGRAPH_DECL_HPP
00030 #define TPETRA_CRSGRAPH_DECL_HPP
00031 
00032 #include <Teuchos_Describable.hpp>
00033 #include <Teuchos_SerialDenseMatrix.hpp>
00034 #include <Teuchos_CompileTimeAssert.hpp>
00035 
00036 #include <Kokkos_DefaultNode.hpp>
00037 #include <Kokkos_DefaultKernels.hpp>
00038 #include <Kokkos_CrsGraph.hpp>
00039 #include <Kokkos_NodeHelpers.hpp>
00040 
00041 #include "Tpetra_ConfigDefs.hpp"
00042 #include "Tpetra_RowGraph.hpp"
00043 #include "Tpetra_DistObject.hpp"
00044 #include "Tpetra_Util.hpp"
00045 
00046 namespace Tpetra {
00047 
00048 #ifndef DOXYGEN_SHOULD_SKIP_THIS
00049   // forward declaration
00050   template <class S, class LO, class GO, class N, class SpMatOps>
00051   class CrsMatrix;
00052 #endif
00053 
00054   struct RowInfo {
00055     size_t localRow;
00056     size_t allocSize;
00057     size_t numEntries;
00058     size_t offset1D;
00059   };
00060 
00061   enum ELocalGlobal {
00062     LocalIndices,
00063     GlobalIndices
00064   };
00065 
00067 
00092   template <class LocalOrdinal, 
00093             class GlobalOrdinal = LocalOrdinal, 
00094             class Node = Kokkos::DefaultNode::DefaultNodeType,
00095             class LocalMatOps = typename Kokkos::DefaultKernels<void,LocalOrdinal,Node>::SparseOps >
00096   class CrsGraph : public RowGraph<LocalOrdinal,GlobalOrdinal,Node>,
00097                    public DistObject<GlobalOrdinal,LocalOrdinal,GlobalOrdinal,Node> {
00098     template <class S, class LO, class GO, class N, class SpMatOps>
00099     friend class CrsMatrix;
00100 
00101     public: 
00102       typedef LocalOrdinal  local_ordinal_type;
00103       typedef GlobalOrdinal global_ordinal_type;
00104       typedef Node          node_type;
00105 
00107 
00108 
00110       CrsGraph(const RCP<const Map<LocalOrdinal,GlobalOrdinal,Node> > &rowMap, size_t maxNumEntriesPerRow, ProfileType pftype = DynamicProfile);
00111 
00113       CrsGraph(const RCP<const Map<LocalOrdinal,GlobalOrdinal,Node> > &rowMap, const ArrayRCP<const size_t> &NumEntriesPerRowToAlloc, ProfileType pftype = DynamicProfile);
00114 
00116 
00118       CrsGraph(const RCP<const Map<LocalOrdinal,GlobalOrdinal,Node> > &rowMap, const RCP<const Map<LocalOrdinal,GlobalOrdinal,Node> > &colMap, size_t maxNumEntriesPerRow, ProfileType pftype = DynamicProfile);
00119 
00121 
00123       CrsGraph(const RCP<const Map<LocalOrdinal,GlobalOrdinal,Node> > &rowMap, const RCP<const Map<LocalOrdinal,GlobalOrdinal,Node> > &colMap, const ArrayRCP<const size_t> &NumEntriesPerRowToAlloc, ProfileType pftype = DynamicProfile);
00124 
00125       // !Destructor.
00126       virtual ~CrsGraph();
00127 
00129 
00131 
00132 
00134 
00145       void insertGlobalIndices(GlobalOrdinal globalRow, const ArrayView<const GlobalOrdinal> &indices);
00146 
00148 
00159       void insertLocalIndices(LocalOrdinal localRow, const ArrayView<const LocalOrdinal> &indices);
00160 
00162 
00171       void removeLocalIndices(LocalOrdinal localRow);
00172 
00174 
00176 
00182 
00184       void globalAssemble();
00185 
00194       void resumeFill();
00195 
00207       void fillComplete(const RCP<const Map<LocalOrdinal,GlobalOrdinal,Node> > &domainMap, const RCP<const Map<LocalOrdinal,GlobalOrdinal,Node> > &rangeMap, OptimizeOption os = DoOptimizeStorage);
00208 
00222       void fillComplete(OptimizeOption os = DoOptimizeStorage);
00223 
00225 
00227 
00228 
00230       const RCP<const Comm<int> > & getComm() const;
00231 
00233       RCP<Node> getNode() const;
00234 
00236       const RCP<const Map<LocalOrdinal,GlobalOrdinal,Node> > & getRowMap() const;
00237 
00239       const RCP<const Map<LocalOrdinal,GlobalOrdinal,Node> > & getColMap() const;
00240 
00242       const RCP<const Map<LocalOrdinal,GlobalOrdinal,Node> > & getDomainMap() const;
00243 
00245       const RCP<const Map<LocalOrdinal,GlobalOrdinal,Node> > & getRangeMap() const;
00246 
00248       RCP<const Import<LocalOrdinal,GlobalOrdinal,Node> > getImporter() const;
00249 
00251       RCP<const Export<LocalOrdinal,GlobalOrdinal,Node> > getExporter() const;
00252 
00254 
00256       global_size_t getGlobalNumRows() const;
00257 
00259 
00261       global_size_t getGlobalNumCols() const;
00262 
00264       size_t getNodeNumRows() const;
00265 
00267 
00269       size_t getNodeNumCols() const;
00270 
00272       GlobalOrdinal getIndexBase() const;
00273 
00275 
00277       global_size_t getGlobalNumEntries() const;
00278 
00280       size_t getNodeNumEntries() const;
00281 
00283 
00284       size_t getNumEntriesInGlobalRow(GlobalOrdinal globalRow) const;
00285 
00287 
00288       size_t getNumEntriesInLocalRow(LocalOrdinal localRow) const;
00289 
00291 
00298       size_t getNodeAllocationSize() const;
00299 
00301 
00302       size_t getNumAllocatedEntriesInGlobalRow(GlobalOrdinal globalRow) const;
00303 
00305 
00306       size_t getNumAllocatedEntriesInLocalRow(LocalOrdinal localRow) const;
00307 
00309 
00311       global_size_t getGlobalNumDiags() const;
00312 
00314 
00316       size_t getNodeNumDiags() const;
00317 
00319 
00321       size_t getGlobalMaxNumRowEntries() const;
00322 
00324 
00326       size_t getNodeMaxNumRowEntries() const;
00327 
00329       bool hasColMap() const; 
00330 
00332 
00334       bool isLowerTriangular() const;
00335 
00337 
00339       bool isUpperTriangular() const;
00340 
00342       bool isLocallyIndexed() const;
00343 
00345       bool isGloballyIndexed() const;
00346 
00348       bool isFillComplete() const;
00349 
00351       bool isFillActive() const;
00352 
00354 
00360       bool isStorageOptimized() const;
00361 
00363       ProfileType getProfileType() const;
00364 
00366 
00375       void getGlobalRowCopy(GlobalOrdinal GlobalRow, 
00376                             const ArrayView<GlobalOrdinal> &Indices, 
00377                             size_t &NumIndices
00378                             ) const;
00379 
00381 
00392       void getLocalRowCopy(LocalOrdinal LocalRow, 
00393                            const ArrayView<LocalOrdinal> &indices, 
00394                            size_t &NumIndices
00395                            ) const;
00396 
00398 
00406       void getGlobalRowView(GlobalOrdinal GlobalRow, ArrayView<const GlobalOrdinal> &Indices) const;
00407 
00409 
00417       void getLocalRowView(LocalOrdinal LocalRow, ArrayView<const LocalOrdinal> &indices) const;
00418 
00420 
00422 
00423 
00425       std::string description() const;
00426 
00428       void describe(Teuchos::FancyOStream &out, const Teuchos::EVerbosityLevel verbLevel=Teuchos::Describable::verbLevel_default) const;
00429 
00431 
00433 
00434 
00435       bool checkSizes(const DistObject<GlobalOrdinal,LocalOrdinal,GlobalOrdinal,Node>& source);
00436 
00437       void copyAndPermute(const DistObject<GlobalOrdinal,LocalOrdinal,GlobalOrdinal,Node> & source,
00438                           size_t numSameIDs,
00439                           const ArrayView<const LocalOrdinal> &permuteToLIDs,
00440                           const ArrayView<const LocalOrdinal> &permuteFromLIDs);
00441 
00442       void packAndPrepare(const DistObject<GlobalOrdinal,LocalOrdinal,GlobalOrdinal,Node> & source,
00443                           const ArrayView<const LocalOrdinal> &exportLIDs,
00444                           Array<GlobalOrdinal> &exports,
00445                           const ArrayView<size_t> & numPacketsPerLID,
00446                           size_t& constantNumPackets,
00447                           Distributor &distor);
00448 
00449       void unpackAndCombine(const ArrayView<const LocalOrdinal> &importLIDs,
00450                             const ArrayView<const GlobalOrdinal> &imports,
00451                             const ArrayView<size_t> &numPacketsPerLID,
00452                             size_t constantNumPackets,
00453                             Distributor &distor,
00454                             CombineMode CM);
00456 
00458 
00459 
00461 
00464       ArrayRCP<const size_t>       getNodeRowBegs() const;
00465 
00467 
00470       ArrayRCP<const LocalOrdinal> getNodePackedIndices() const;
00471 
00473 
00475 
00476 
00485       TPETRA_DEPRECATED void optimizeStorage();
00486 
00488       TPETRA_DEPRECATED ArrayRCP<const GlobalOrdinal> getGlobalRowView(GlobalOrdinal GlobalRow) const;
00489 
00491       TPETRA_DEPRECATED ArrayRCP<const LocalOrdinal> getLocalRowView(LocalOrdinal LocalRow) const;
00492 
00494 
00495     private:
00496       // copy constructor disabled
00497       CrsGraph(const CrsGraph<LocalOrdinal,GlobalOrdinal,Node> &Source);
00498       // operator= disabled
00499       CrsGraph<LocalOrdinal,GlobalOrdinal,Node> & operator=(const CrsGraph<LocalOrdinal,GlobalOrdinal,Node> &rhs);
00500     protected:
00501       // these structs are conveniences, to cut down on the number of argument to some of the methods below.
00502       struct SLocalGlobalViews {
00503         ArrayView<const GlobalOrdinal> ginds;
00504         ArrayView<const LocalOrdinal>  linds;
00505       };
00506       struct SLocalGlobalNCViews {
00507         ArrayView<GlobalOrdinal>       ginds;
00508         ArrayView<LocalOrdinal>        linds;
00509       };
00510       // Allocation
00511       bool                                     indicesAreAllocated() const;
00512       void                                     allocateIndices(ELocalGlobal lg);
00513       template <class T>                  void allocateValues(ArrayRCP<T> &values1D, ArrayRCP<ArrayRCP<T> > &values2D) const;
00514       template <ELocalGlobal lg>          RowInfo updateAlloc(RowInfo rowinfo, size_t allocSize);
00515       template <ELocalGlobal lg, class T> RowInfo updateAllocAndValues(RowInfo rowinfo, size_t allocSize, ArrayRCP<T> &rowVals);
00516       // Local versus global indices
00517       void computeIndexState();
00518       void makeColMap();
00519       void makeIndicesLocal();
00520       void makeImportExport();
00521       // insert/suminto/replace
00522       template <ELocalGlobal lg>                           size_t                filterIndices         (const SLocalGlobalNCViews &inds) const;
00523       template <ELocalGlobal lg, class T>                  size_t                filterIndicesAndValues(const SLocalGlobalNCViews &inds, const ArrayView<T> &vals) const;
00524       template <ELocalGlobal lg>                           size_t                insertIndices         (RowInfo rowInfo, const SLocalGlobalViews &newInds);
00525       template <ELocalGlobal lg, class IterO, class IterN> void                  insertIndicesAndValues(RowInfo rowInfo, const SLocalGlobalViews &newInds, IterO rowVals, IterN newVals);
00526       template <ELocalGlobal lg, class IterO, class IterN, class BinaryFunction> void   transformValues(RowInfo rowInfo, const SLocalGlobalViews &inds,    IterO rowVals, IterN newVals, BinaryFunction f) const;
00527       // Sorting and merging
00528       bool                       isSorted() const;
00529       bool                       isMerged() const;
00530       void                       setSorted(bool sorted);
00531       void                       setMerged(bool merged);
00532       void                       sortAllIndices();
00533       void                       sortRowIndices(RowInfo rowinfo);
00534       template <class Iter> void sortRowIndicesAndValues(RowInfo rowinfo, Iter rowValueIter);
00535       void                                             mergeAllIndices();
00536       void                                             mergeRowIndices(RowInfo rowinfo);
00537       template <class Iter, class BinaryFunction> void mergeRowIndicesAndValues(RowInfo rowinfo, Iter rowValueIter, BinaryFunction f);
00538       // 
00539       void setDomainRangeMaps(const RCP<const Map<LocalOrdinal,GlobalOrdinal,Node> > &domainMap, const RCP<const Map<LocalOrdinal,GlobalOrdinal,Node> > &rangeMap);
00540       void staticAssertions() const;
00541       // global consts
00542       void clearGlobalConstants();
00543       void computeGlobalConstants();
00544       // graph data accessors
00545       RowInfo                         getRowInfo(size_t myRow) const;
00546       ArrayView<const LocalOrdinal>   getLocalView(RowInfo rowinfo) const;
00547       ArrayView<LocalOrdinal>         getLocalViewNonConst(RowInfo rowinfo);
00548       ArrayView<const GlobalOrdinal>  getGlobalView(RowInfo rowinfo) const;
00549       ArrayView<GlobalOrdinal>        getGlobalViewNonConst(RowInfo rowinfo);
00550       size_t                          findLocalIndex(RowInfo rowinfo, LocalOrdinal ind) const;
00551       size_t                          findGlobalIndex(RowInfo rowinfo, GlobalOrdinal ind) const;
00552       // local Kokkos objects
00553       void pushToLocalGraph();
00554       void pullFromLocalGraph();
00555       void fillLocalGraph(OptimizeOption os);
00556       const Kokkos::CrsGraph<LocalOrdinal,Node,LocalMatOps> & getLocalGraph() const;
00557       Kokkos::CrsGraph<LocalOrdinal,Node,LocalMatOps>       & getLocalGraphNonConst();
00558       // debugging
00559       void checkInternalState() const;
00560 
00561       // Tpetra support objects
00562       RCP<const Map<LocalOrdinal,GlobalOrdinal,Node> > rowMap_, colMap_, rangeMap_, domainMap_;
00563       RCP<Import<LocalOrdinal,GlobalOrdinal,Node> > importer_;
00564       RCP<Export<LocalOrdinal,GlobalOrdinal,Node> > exporter_;
00565 
00566       // local data, stored in a Kokkos::CrsGraph. only initialized after fillComplete()
00567       Kokkos::CrsGraph<LocalOrdinal,Node,LocalMatOps> lclGraph_;
00568 
00569       // Local and Global Counts
00570       // nodeNumEntries_ and nodeNumAllocated_ are required to be always consistent
00571       // nodeMaxNumEntries_, nodeNumDiags_ and the global quantities are computed during fillComplete() and only valid when isFillComplete()
00572       global_size_t globalNumEntries_, globalNumDiags_, globalMaxNumRowEntries_;
00573       size_t          nodeNumEntries_,   nodeNumDiags_,   nodeMaxNumRowEntries_, nodeNumAllocated_;
00574 
00575       // allocate static or dynamic?
00576       ProfileType pftype_;
00577       // requested allocation sizes; we have to preserve these, because we perform late-allocation
00578       // number of non-zeros to allocate per row; set to null after they are allocated.
00579       ArrayRCP<const size_t> numAllocPerRow_;
00580       // number of non-zeros to allocate for all row; either this or numAllocPerRow_ is used, but not both.
00581       size_t numAllocForAllRows_;
00582 
00583       // graph indices. before allocation, all are null. 
00584       // after allocation, except during makeIndicesLocal(), one of local or global is null.
00585       // we will never have 1D and 2D structures being non-null
00586       // this is host memory
00587       // 1D == StaticAllocation, 2D == DynamicAllocation
00589       //
00590       // 1D/Static structures
00591       //
00594       ArrayRCP< LocalOrdinal>                     lclInds1D_;
00596       ArrayRCP<GlobalOrdinal>                     gblInds1D_;
00597       // offset to the beg and end entries of each row. only used for 1D (Static) allocation.
00598       // i.e., indices for row R are lclInds1D_[i] for i in [b,e) where b = rowBegs_[R] and e = rowEnds_[R]
00599       // for a packed (optimized) allocation, we will typically have &rowBegs_[R]+1 == &rowEnds_[R]
00600       // these are null for 2D (Dynamic) allocations
00601       // the allocation size is computed by looking at the difference between rowBegs_[r+1] and rowBegs_[r]
00602       // rowBegs_ therefore has length N+1, while rowEnds_ has length N
00603       ArrayRCP<size_t> rowBegs_, rowEnds_;
00605       //
00606       // 2D/Dynamic structures. 
00607       //
00610       ArrayRCP<ArrayRCP< LocalOrdinal> > lclInds2D_;
00612       ArrayRCP<ArrayRCP<GlobalOrdinal> > gblInds2D_;
00614       ArrayRCP<size_t>       numEntriesPerRow_;
00615 
00616       // TODO: these might be useful in the future
00617       // ArrayRCP< typedef ArrayRCP<const GlobalOrdinal>::iterator > gRowPtrs_;
00618       // ArrayRCP< typedef ArrayRCP<GlobalOrdinal>::iterator > gRowPtrsNC_;
00619       // ArrayRCP< typedef ArrayRCP<const LocalOrdinal>::iterator > lRowPtrs_;
00620       // ArrayRCP< typedef ArrayRCP<LocalOrdinal>::iterator > lRowPtrsNC_;
00621 
00622       bool indicesAreAllocated_,
00623            indicesAreLocal_,
00624            indicesAreGlobal_,
00625            fillComplete_, 
00626            lowerTriangular_,
00627            upperTriangular_,
00628            indicesAreSorted_,
00629            noRedundancies_,
00630            haveGlobalConstants_;
00631 
00632       // non-local data
00633       std::map<GlobalOrdinal, std::deque<GlobalOrdinal> > nonlocals_;
00634 
00635   }; // class CrsGraph
00636 
00637 } // namespace Tpetra
00638 
00639 #endif