Tpetra Matrix/Vector Services Version of the Day
Tpetra_CrsGraph_decl.hpp
00001 // @HEADER
00002 // ***********************************************************************
00003 // 
00004 //          Tpetra: Templated Linear Algebra Services Package
00005 //                 Copyright (2008) Sandia Corporation
00006 // 
00007 // Under the terms of Contract DE-AC04-94AL85000 with Sandia Corporation,
00008 // the U.S. Government retains certain rights in this software.
00009 // 
00010 // Redistribution and use in source and binary forms, with or without
00011 // modification, are permitted provided that the following conditions are
00012 // met:
00013 //
00014 // 1. Redistributions of source code must retain the above copyright
00015 // notice, this list of conditions and the following disclaimer.
00016 //
00017 // 2. Redistributions in binary form must reproduce the above copyright
00018 // notice, this list of conditions and the following disclaimer in the
00019 // documentation and/or other materials provided with the distribution.
00020 //
00021 // 3. Neither the name of the Corporation nor the names of the
00022 // contributors may be used to endorse or promote products derived from
00023 // this software without specific prior written permission.
00024 //
00025 // THIS SOFTWARE IS PROVIDED BY SANDIA CORPORATION "AS IS" AND ANY
00026 // EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
00027 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
00028 // PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL SANDIA CORPORATION OR THE
00029 // CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
00030 // EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
00031 // PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
00032 // PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
00033 // LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
00034 // NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
00035 // SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00036 //
00037 // Questions? Contact Michael A. Heroux (maherou@sandia.gov) 
00038 // 
00039 // ************************************************************************
00040 // @HEADER
00041 
00042 #ifndef TPETRA_CRSGRAPH_DECL_HPP
00043 #define TPETRA_CRSGRAPH_DECL_HPP
00044 
00045 #include <Teuchos_Describable.hpp>
00046 #include <Teuchos_CompileTimeAssert.hpp>
00047 
00048 #include <Kokkos_DefaultNode.hpp>
00049 #include <Kokkos_DefaultKernels.hpp>
00050 #include <Kokkos_CrsGraph.hpp>
00051 #include <Kokkos_NodeHelpers.hpp>
00052 
00053 #include "Tpetra_ConfigDefs.hpp"
00054 #include "Tpetra_RowGraph.hpp"
00055 #include "Tpetra_DistObject.hpp"
00056 #include "Tpetra_Util.hpp"
00057 
00058 namespace Tpetra {
00059 
00060 #ifndef DOXYGEN_SHOULD_SKIP_THIS
00061   // forward declaration
00062   template <class S, class LO, class GO, class N, class SpMatOps>
00063   class CrsMatrix;
00064 #endif
00065 
00066   struct RowInfo {
00067     size_t localRow;
00068     size_t allocSize;
00069     size_t numEntries;
00070     size_t offset1D;
00071   };
00072 
00073   enum ELocalGlobal {
00074     LocalIndices,
00075     GlobalIndices
00076   };
00077 
00079 
00104   template <class LocalOrdinal, 
00105             class GlobalOrdinal = LocalOrdinal, 
00106             class Node = Kokkos::DefaultNode::DefaultNodeType,
00107             class LocalMatOps = typename Kokkos::DefaultKernels<void,LocalOrdinal,Node>::SparseOps >
00108   class CrsGraph : public RowGraph<LocalOrdinal,GlobalOrdinal,Node>,
00109                    public DistObject<GlobalOrdinal,LocalOrdinal,GlobalOrdinal,Node> {
00110     template <class S, class LO, class GO, class N, class SpMatOps>
00111     friend class CrsMatrix;
00112 
00113     public: 
00114       typedef LocalOrdinal  local_ordinal_type;
00115       typedef GlobalOrdinal global_ordinal_type;
00116       typedef Node          node_type;
00117 
00119 
00120 
00122       CrsGraph(const RCP<const Map<LocalOrdinal,GlobalOrdinal,Node> > &rowMap, size_t maxNumEntriesPerRow, ProfileType pftype = DynamicProfile);
00123 
00125       CrsGraph(const RCP<const Map<LocalOrdinal,GlobalOrdinal,Node> > &rowMap, const ArrayRCP<const size_t> &NumEntriesPerRowToAlloc, ProfileType pftype = DynamicProfile);
00126 
00128 
00130       CrsGraph(const RCP<const Map<LocalOrdinal,GlobalOrdinal,Node> > &rowMap, const RCP<const Map<LocalOrdinal,GlobalOrdinal,Node> > &colMap, size_t maxNumEntriesPerRow, ProfileType pftype = DynamicProfile);
00131 
00133 
00135       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);
00136 
00137       // !Destructor.
00138       virtual ~CrsGraph();
00139 
00141 
00143 
00144 
00146 
00157       void insertGlobalIndices(GlobalOrdinal globalRow, const ArrayView<const GlobalOrdinal> &indices);
00158 
00160 
00171       void insertLocalIndices(LocalOrdinal localRow, const ArrayView<const LocalOrdinal> &indices);
00172 
00174 
00183       void removeLocalIndices(LocalOrdinal localRow);
00184 
00186 
00188 
00194 
00196       void globalAssemble();
00197 
00206       void resumeFill();
00207 
00219       void fillComplete(const RCP<const Map<LocalOrdinal,GlobalOrdinal,Node> > &domainMap, const RCP<const Map<LocalOrdinal,GlobalOrdinal,Node> > &rangeMap, OptimizeOption os = DoOptimizeStorage);
00220 
00234       void fillComplete(OptimizeOption os = DoOptimizeStorage);
00235 
00237 
00239 
00240 
00242       const RCP<const Comm<int> > & getComm() const;
00243 
00245       RCP<Node> getNode() const;
00246 
00248       const RCP<const Map<LocalOrdinal,GlobalOrdinal,Node> > & getRowMap() const;
00249 
00251       const RCP<const Map<LocalOrdinal,GlobalOrdinal,Node> > & getColMap() const;
00252 
00254       const RCP<const Map<LocalOrdinal,GlobalOrdinal,Node> > & getDomainMap() const;
00255 
00257       const RCP<const Map<LocalOrdinal,GlobalOrdinal,Node> > & getRangeMap() const;
00258 
00260       RCP<const Import<LocalOrdinal,GlobalOrdinal,Node> > getImporter() const;
00261 
00263       RCP<const Export<LocalOrdinal,GlobalOrdinal,Node> > getExporter() const;
00264 
00266 
00268       global_size_t getGlobalNumRows() const;
00269 
00271 
00274       global_size_t getGlobalNumCols() const;
00275 
00277       size_t getNodeNumRows() const;
00278 
00280 
00282       size_t getNodeNumCols() const;
00283 
00285       GlobalOrdinal getIndexBase() const;
00286 
00288 
00290       global_size_t getGlobalNumEntries() const;
00291 
00293       size_t getNodeNumEntries() const;
00294 
00296 
00297       size_t getNumEntriesInGlobalRow(GlobalOrdinal globalRow) const;
00298 
00300 
00301       size_t getNumEntriesInLocalRow(LocalOrdinal localRow) const;
00302 
00304 
00311       size_t getNodeAllocationSize() const;
00312 
00314 
00315       size_t getNumAllocatedEntriesInGlobalRow(GlobalOrdinal globalRow) const;
00316 
00318 
00319       size_t getNumAllocatedEntriesInLocalRow(LocalOrdinal localRow) const;
00320 
00322 
00324       global_size_t getGlobalNumDiags() const;
00325 
00327 
00329       size_t getNodeNumDiags() const;
00330 
00332 
00334       size_t getGlobalMaxNumRowEntries() const;
00335 
00337 
00339       size_t getNodeMaxNumRowEntries() const;
00340 
00342       bool hasColMap() const; 
00343 
00345 
00347       bool isLowerTriangular() const;
00348 
00350 
00352       bool isUpperTriangular() const;
00353 
00355       bool isLocallyIndexed() const;
00356 
00358       bool isGloballyIndexed() const;
00359 
00361       bool isFillComplete() const;
00362 
00364       bool isFillActive() const;
00365 
00367 
00370       bool isSorted() const;
00371 
00373 
00379       bool isStorageOptimized() const;
00380 
00382       ProfileType getProfileType() const;
00383 
00385 
00394       void getGlobalRowCopy(GlobalOrdinal GlobalRow, 
00395                             const ArrayView<GlobalOrdinal> &Indices, 
00396                             size_t &NumIndices
00397                             ) const;
00398 
00400 
00411       void getLocalRowCopy(LocalOrdinal LocalRow, 
00412                            const ArrayView<LocalOrdinal> &indices, 
00413                            size_t &NumIndices
00414                            ) const;
00415 
00417 
00425       void getGlobalRowView(GlobalOrdinal GlobalRow, ArrayView<const GlobalOrdinal> &Indices) const;
00426 
00428 
00436       void getLocalRowView(LocalOrdinal LocalRow, ArrayView<const LocalOrdinal> &indices) const;
00437 
00439 
00441 
00442 
00444       std::string description() const;
00445 
00447       void describe(Teuchos::FancyOStream &out, const Teuchos::EVerbosityLevel verbLevel=Teuchos::Describable::verbLevel_default) const;
00448 
00450 
00452 
00453 
00454       bool checkSizes(const DistObject<GlobalOrdinal,LocalOrdinal,GlobalOrdinal,Node>& source);
00455 
00456       void copyAndPermute(const DistObject<GlobalOrdinal,LocalOrdinal,GlobalOrdinal,Node> & source,
00457                           size_t numSameIDs,
00458                           const ArrayView<const LocalOrdinal> &permuteToLIDs,
00459                           const ArrayView<const LocalOrdinal> &permuteFromLIDs);
00460 
00461       void packAndPrepare(const DistObject<GlobalOrdinal,LocalOrdinal,GlobalOrdinal,Node> & source,
00462                           const ArrayView<const LocalOrdinal> &exportLIDs,
00463                           Array<GlobalOrdinal> &exports,
00464                           const ArrayView<size_t> & numPacketsPerLID,
00465                           size_t& constantNumPackets,
00466                           Distributor &distor);
00467 
00468       void unpackAndCombine(const ArrayView<const LocalOrdinal> &importLIDs,
00469                             const ArrayView<const GlobalOrdinal> &imports,
00470                             const ArrayView<size_t> &numPacketsPerLID,
00471                             size_t constantNumPackets,
00472                             Distributor &distor,
00473                             CombineMode CM);
00475 
00477 
00478 
00480 
00483       ArrayRCP<const size_t>       getNodeRowBegs() const;
00484 
00486 
00489       ArrayRCP<const LocalOrdinal> getNodePackedIndices() const;
00490 
00492 
00494 
00495 
00504       TPETRA_DEPRECATED void optimizeStorage();
00505 
00507       TPETRA_DEPRECATED ArrayRCP<const GlobalOrdinal> getGlobalRowView(GlobalOrdinal GlobalRow) const;
00508 
00510       TPETRA_DEPRECATED ArrayRCP<const LocalOrdinal> getLocalRowView(LocalOrdinal LocalRow) const;
00511 
00513 
00514     private:
00515       // copy constructor disabled
00516       CrsGraph(const CrsGraph<LocalOrdinal,GlobalOrdinal,Node> &Source);
00517       // operator= disabled
00518       CrsGraph<LocalOrdinal,GlobalOrdinal,Node> & operator=(const CrsGraph<LocalOrdinal,GlobalOrdinal,Node> &rhs);
00519     protected:
00520       // these structs are conveniences, to cut down on the number of argument to some of the methods below.
00521       struct SLocalGlobalViews {
00522         ArrayView<const GlobalOrdinal> ginds;
00523         ArrayView<const LocalOrdinal>  linds;
00524       };
00525       struct SLocalGlobalNCViews {
00526         ArrayView<GlobalOrdinal>       ginds;
00527         ArrayView<LocalOrdinal>        linds;
00528       };
00529       // Allocation
00530       bool                                     indicesAreAllocated() const;
00531       void                                     allocateIndices(ELocalGlobal lg);
00532       template <class T>                  void allocateValues(ArrayRCP<T> &values1D, ArrayRCP<ArrayRCP<T> > &values2D) const;
00533       template <ELocalGlobal lg>          RowInfo updateAlloc(RowInfo rowinfo, size_t allocSize);
00534       template <ELocalGlobal lg, class T> RowInfo updateAllocAndValues(RowInfo rowinfo, size_t allocSize, ArrayRCP<T> &rowVals);
00535       // Local versus global indices
00536       void computeIndexState();
00537       void makeColMap();
00538       void makeIndicesLocal();
00539       void makeImportExport();
00540       // insert/suminto/replace
00541       template <ELocalGlobal lg>                           size_t                filterIndices         (const SLocalGlobalNCViews &inds) const;
00542       template <ELocalGlobal lg, class T>                  size_t                filterIndicesAndValues(const SLocalGlobalNCViews &inds, const ArrayView<T> &vals) const;
00543       template <ELocalGlobal lg, ELocalGlobal I>                           size_t       insertIndices         (RowInfo rowInfo, const SLocalGlobalViews &newInds);
00544       template <ELocalGlobal lg, ELocalGlobal I, class IterO, class IterN> void         insertIndicesAndValues(RowInfo rowInfo, const SLocalGlobalViews &newInds, IterO rowVals, IterN newVals);
00545       template <ELocalGlobal lg, class IterO, class IterN, class BinaryFunction> void   transformValues(RowInfo rowInfo, const SLocalGlobalViews &inds,    IterO rowVals, IterN newVals, BinaryFunction f) const;
00546       // Sorting and merging
00547       bool                       isMerged() const;
00548       void                       setSorted(bool sorted);
00549       void                       setMerged(bool merged);
00550       void                       sortAllIndices();
00551       void                       sortRowIndices(RowInfo rowinfo);
00552       template <class Scalar> void sortRowIndicesAndValues(RowInfo rowinfo, ArrayView<Scalar> values);
00553       void                                             mergeAllIndices();
00554       void                                             mergeRowIndices(RowInfo rowinfo);
00555       template <class Iter, class BinaryFunction> void mergeRowIndicesAndValues(RowInfo rowinfo, Iter rowValueIter, BinaryFunction f);
00556       // 
00557       void setDomainRangeMaps(const RCP<const Map<LocalOrdinal,GlobalOrdinal,Node> > &domainMap, const RCP<const Map<LocalOrdinal,GlobalOrdinal,Node> > &rangeMap);
00558       void staticAssertions() const;
00559       // global consts
00560       void clearGlobalConstants();
00561       void computeGlobalConstants();
00562       // graph data accessors
00563       RowInfo                         getRowInfo(size_t myRow) const;
00564       ArrayView<const LocalOrdinal>   getLocalView(RowInfo rowinfo) const;
00565       ArrayView<LocalOrdinal>         getLocalViewNonConst(RowInfo rowinfo);
00566       ArrayView<const GlobalOrdinal>  getGlobalView(RowInfo rowinfo) const;
00567       ArrayView<GlobalOrdinal>        getGlobalViewNonConst(RowInfo rowinfo);
00568       size_t                          findLocalIndex(RowInfo rowinfo, LocalOrdinal ind) const;
00569       size_t                          findGlobalIndex(RowInfo rowinfo, GlobalOrdinal ind) const;
00570       // local Kokkos objects
00571       void pushToLocalGraph();
00572       void pullFromLocalGraph();
00573       void fillLocalGraph(OptimizeOption os);
00574       const Kokkos::CrsGraph<LocalOrdinal,Node,LocalMatOps> & getLocalGraph() const;
00575       Kokkos::CrsGraph<LocalOrdinal,Node,LocalMatOps>       & getLocalGraphNonConst();
00576       // debugging
00577       void checkInternalState() const;
00578 
00579       // Tpetra support objects
00580       RCP<const Map<LocalOrdinal,GlobalOrdinal,Node> > rowMap_, colMap_, rangeMap_, domainMap_;
00581       RCP<Import<LocalOrdinal,GlobalOrdinal,Node> > importer_;
00582       RCP<Export<LocalOrdinal,GlobalOrdinal,Node> > exporter_;
00583 
00584       // local data, stored in a Kokkos::CrsGraph. only initialized after fillComplete()
00585       Kokkos::CrsGraph<LocalOrdinal,Node,LocalMatOps> lclGraph_;
00586 
00587       // Local and Global Counts
00588       // nodeNumEntries_ and nodeNumAllocated_ are required to be always consistent
00589       // nodeMaxNumEntries_, nodeNumDiags_ and the global quantities are computed during fillComplete() and only valid when isFillComplete()
00590       global_size_t globalNumEntries_, globalNumDiags_, globalMaxNumRowEntries_;
00591       size_t          nodeNumEntries_,   nodeNumDiags_,   nodeMaxNumRowEntries_, nodeNumAllocated_;
00592 
00593       // allocate static or dynamic?
00594       ProfileType pftype_;
00595       // requested allocation sizes; we have to preserve these, because we perform late-allocation
00596       // number of non-zeros to allocate per row; set to null after they are allocated.
00597       ArrayRCP<const size_t> numAllocPerRow_;
00598       // number of non-zeros to allocate for all row; either this or numAllocPerRow_ is used, but not both.
00599       size_t numAllocForAllRows_;
00600 
00601       // graph indices. before allocation, all are null. 
00602       // after allocation, except during makeIndicesLocal(), one of local or global is null.
00603       // we will never have 1D and 2D structures being non-null
00604       // this is host memory
00605       // 1D == StaticAllocation, 2D == DynamicAllocation
00607       //
00608       // 1D/Static structures
00609       //
00612       ArrayRCP< LocalOrdinal>                     lclInds1D_;
00614       ArrayRCP<GlobalOrdinal>                     gblInds1D_;
00615       // offset to the beg and end entries of each row. only used for 1D (Static) allocation.
00616       // i.e., indices for row R are lclInds1D_[i] for i in [b,e) where b = rowBegs_[R] and e = rowEnds_[R]
00617       // for a packed (optimized) allocation, we will typically have &rowBegs_[R]+1 == &rowEnds_[R]
00618       // these are null for 2D (Dynamic) allocations
00619       // the allocation size is computed by looking at the difference between rowBegs_[r+1] and rowBegs_[r]
00620       // rowBegs_ therefore has length N+1, while rowEnds_ has length N
00621       ArrayRCP<size_t> rowBegs_, rowEnds_;
00623       //
00624       // 2D/Dynamic structures. 
00625       //
00628       ArrayRCP<ArrayRCP< LocalOrdinal> > lclInds2D_;
00630       ArrayRCP<ArrayRCP<GlobalOrdinal> > gblInds2D_;
00632       ArrayRCP<size_t>       numEntriesPerRow_;
00633 
00634       // TODO: these might be useful in the future
00635       // ArrayRCP< typedef ArrayRCP<const GlobalOrdinal>::iterator > gRowPtrs_;
00636       // ArrayRCP< typedef ArrayRCP<GlobalOrdinal>::iterator > gRowPtrsNC_;
00637       // ArrayRCP< typedef ArrayRCP<const LocalOrdinal>::iterator > lRowPtrs_;
00638       // ArrayRCP< typedef ArrayRCP<LocalOrdinal>::iterator > lRowPtrsNC_;
00639 
00640       bool indicesAreAllocated_,
00641            indicesAreLocal_,
00642            indicesAreGlobal_,
00643            fillComplete_, 
00644            lowerTriangular_,
00645            upperTriangular_,
00646            indicesAreSorted_,
00647            noRedundancies_,
00648            haveGlobalConstants_;
00649 
00650       // non-local data
00651       std::map<GlobalOrdinal, std::deque<GlobalOrdinal> > nonlocals_;
00652 
00653   }; // class CrsGraph
00654 
00655 } // namespace Tpetra
00656 
00657 #endif
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines