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 
00051 #include "Tpetra_ConfigDefs.hpp"
00052 #include "Tpetra_RowGraph.hpp"
00053 #include "Tpetra_DistObject.hpp"
00054 #include "Tpetra_Util.hpp"
00055 
00056 namespace Tpetra {
00057 
00058 #ifndef DOXYGEN_SHOULD_SKIP_THIS
00059   // forward declaration
00060   template <class S, class LO, class GO, class N, class SpMatOps>
00061   class CrsMatrix;
00062 #endif
00063 
00064   struct RowInfo {
00065     size_t localRow;
00066     size_t allocSize;
00067     size_t numEntries;
00068     size_t offset1D;
00069   };
00070 
00071   enum ELocalGlobal {
00072     LocalIndices,
00073     GlobalIndices
00074   };
00075 
00077 
00121   template <class LocalOrdinal,
00122             class GlobalOrdinal = LocalOrdinal,
00123             class Node = Kokkos::DefaultNode::DefaultNodeType,
00124             class LocalMatOps = typename Kokkos::DefaultKernels<void,LocalOrdinal,Node>::SparseOps >
00125   class CrsGraph :
00126     public RowGraph<LocalOrdinal,GlobalOrdinal,Node>,
00127     public DistObject<GlobalOrdinal,LocalOrdinal,GlobalOrdinal,Node>,
00128     public Teuchos::ParameterListAcceptorDefaultBase
00129   {
00130     template <class S, class LO, class GO, class N, class SpMatOps>
00131     friend class CrsMatrix;
00132 
00133   public:
00134     typedef LocalOrdinal                         local_ordinal_type;
00135     typedef GlobalOrdinal                        global_ordinal_type;
00136     typedef Node                                 node_type;
00137     typedef Map<LocalOrdinal,GlobalOrdinal,Node> map_type;
00138 
00140 
00141 
00159     CrsGraph (const RCP<const map_type>& rowMap,
00160               size_t maxNumEntriesPerRow,
00161               ProfileType pftype = DynamicProfile,
00162               const RCP<ParameterList>& params = null);
00163 
00181     CrsGraph (const RCP<const Map<LocalOrdinal,GlobalOrdinal,Node> >& rowMap,
00182               const ArrayRCP<const size_t>& NumEntriesPerRowToAlloc,
00183               ProfileType pftype = DynamicProfile,
00184               const RCP<ParameterList>& params = null);
00185 
00208     CrsGraph (const RCP<const Map<LocalOrdinal,GlobalOrdinal,Node> >& rowMap,
00209               const RCP<const Map<LocalOrdinal,GlobalOrdinal,Node> >& colMap,
00210               size_t maxNumEntriesPerRow,
00211               ProfileType pftype = DynamicProfile,
00212               const RCP<ParameterList>& params = null);
00213 
00236     CrsGraph (const RCP<const Map<LocalOrdinal,GlobalOrdinal,Node> >& rowMap,
00237               const RCP<const Map<LocalOrdinal,GlobalOrdinal,Node> >& colMap,
00238               const ArrayRCP<const size_t> &NumEntriesPerRowToAlloc,
00239               ProfileType pftype = DynamicProfile,
00240               const RCP<ParameterList>& params = null);
00241 
00243     virtual ~CrsGraph();
00244 
00246 
00248 
00249 
00251     void setParameterList (const RCP<ParameterList>& params);
00252 
00254     RCP<const ParameterList> getValidParameters () const;
00255 
00257 
00259 
00260 
00262 
00273       void insertGlobalIndices(GlobalOrdinal globalRow, const ArrayView<const GlobalOrdinal> &indices);
00274 
00276 
00287       void insertLocalIndices(LocalOrdinal localRow, const ArrayView<const LocalOrdinal> &indices);
00288 
00290 
00299       void removeLocalIndices(LocalOrdinal localRow);
00300 
00302 
00304 
00310 
00312       void globalAssemble();
00313 
00322       void resumeFill(const RCP<ParameterList> &params = null);
00323 
00335       void fillComplete(const RCP<const Map<LocalOrdinal,GlobalOrdinal,Node> > &domainMap, const RCP<const Map<LocalOrdinal,GlobalOrdinal,Node> > &rangeMap, const RCP<ParameterList> &params = null);
00336 
00350       void fillComplete(const RCP<ParameterList> &params = null);
00351 
00353 
00355 
00356 
00358       const RCP<const Comm<int> > & getComm() const;
00359 
00361       RCP<Node> getNode() const;
00362 
00364       const RCP<const Map<LocalOrdinal,GlobalOrdinal,Node> > & getRowMap() const;
00365 
00367       const RCP<const Map<LocalOrdinal,GlobalOrdinal,Node> > & getColMap() const;
00368 
00370       const RCP<const Map<LocalOrdinal,GlobalOrdinal,Node> > & getDomainMap() const;
00371 
00373       const RCP<const Map<LocalOrdinal,GlobalOrdinal,Node> > & getRangeMap() const;
00374 
00376       RCP<const Import<LocalOrdinal,GlobalOrdinal,Node> > getImporter() const;
00377 
00379       RCP<const Export<LocalOrdinal,GlobalOrdinal,Node> > getExporter() const;
00380 
00382 
00384       global_size_t getGlobalNumRows() const;
00385 
00387 
00390       global_size_t getGlobalNumCols() const;
00391 
00393       size_t getNodeNumRows() const;
00394 
00396 
00398       size_t getNodeNumCols() const;
00399 
00401       GlobalOrdinal getIndexBase() const;
00402 
00404 
00406       global_size_t getGlobalNumEntries() const;
00407 
00409       size_t getNodeNumEntries() const;
00410 
00412 
00413       size_t getNumEntriesInGlobalRow(GlobalOrdinal globalRow) const;
00414 
00416 
00417       size_t getNumEntriesInLocalRow(LocalOrdinal localRow) const;
00418 
00420 
00427       size_t getNodeAllocationSize() const;
00428 
00430 
00431       size_t getNumAllocatedEntriesInGlobalRow(GlobalOrdinal globalRow) const;
00432 
00434 
00435       size_t getNumAllocatedEntriesInLocalRow(LocalOrdinal localRow) const;
00436 
00438 
00440       global_size_t getGlobalNumDiags() const;
00441 
00443 
00445       size_t getNodeNumDiags() const;
00446 
00448 
00450       size_t getGlobalMaxNumRowEntries() const;
00451 
00453 
00455       size_t getNodeMaxNumRowEntries() const;
00456 
00458       bool hasColMap() const;
00459 
00461 
00463       bool isLowerTriangular() const;
00464 
00466 
00468       bool isUpperTriangular() const;
00469 
00471       bool isLocallyIndexed() const;
00472 
00474       bool isGloballyIndexed() const;
00475 
00477       bool isFillComplete() const;
00478 
00480       bool isFillActive() const;
00481 
00483 
00486       bool isSorted() const;
00487 
00489 
00495       bool isStorageOptimized() const;
00496 
00498       ProfileType getProfileType() const;
00499 
00501 
00510       void getGlobalRowCopy(GlobalOrdinal GlobalRow,
00511                             const ArrayView<GlobalOrdinal> &Indices,
00512                             size_t &NumIndices
00513                             ) const;
00514 
00516 
00527       void getLocalRowCopy(LocalOrdinal LocalRow,
00528                            const ArrayView<LocalOrdinal> &indices,
00529                            size_t &NumIndices
00530                            ) const;
00531 
00533 
00541       void getGlobalRowView(GlobalOrdinal GlobalRow, ArrayView<const GlobalOrdinal> &Indices) const;
00542 
00544 
00552       void getLocalRowView(LocalOrdinal LocalRow, ArrayView<const LocalOrdinal> &indices) const;
00553 
00555 
00557 
00558 
00560       std::string description() const;
00561 
00563       void describe(Teuchos::FancyOStream &out, const Teuchos::EVerbosityLevel verbLevel=Teuchos::Describable::verbLevel_default) const;
00564 
00566 
00568 
00569 
00570       bool checkSizes(const DistObject<GlobalOrdinal,LocalOrdinal,GlobalOrdinal,Node>& source);
00571 
00572       void copyAndPermute(const DistObject<GlobalOrdinal,LocalOrdinal,GlobalOrdinal,Node> & source,
00573                           size_t numSameIDs,
00574                           const ArrayView<const LocalOrdinal> &permuteToLIDs,
00575                           const ArrayView<const LocalOrdinal> &permuteFromLIDs);
00576 
00577       void packAndPrepare(const DistObject<GlobalOrdinal,LocalOrdinal,GlobalOrdinal,Node> & source,
00578                           const ArrayView<const LocalOrdinal> &exportLIDs,
00579                           Array<GlobalOrdinal> &exports,
00580                           const ArrayView<size_t> & numPacketsPerLID,
00581                           size_t& constantNumPackets,
00582                           Distributor &distor);
00583 
00584       void unpackAndCombine(const ArrayView<const LocalOrdinal> &importLIDs,
00585                             const ArrayView<const GlobalOrdinal> &imports,
00586                             const ArrayView<size_t> &numPacketsPerLID,
00587                             size_t constantNumPackets,
00588                             Distributor &distor,
00589                             CombineMode CM);
00591 
00593 
00594 
00596 
00599       ArrayRCP<const size_t> getNodeRowPtrs() const;
00600 
00602 
00604       ArrayRCP<const LocalOrdinal> getNodePackedIndices() const;
00605 
00607 
00608     private:
00609       // We forbid copy construction by declaring this method private
00610       // and not implementing it.
00611       CrsGraph (const CrsGraph<LocalOrdinal,GlobalOrdinal,Node> &Source);
00612 
00613       // We forbid assignment (operator=) by declaring this method
00614       // private and not implementing it.
00615       CrsGraph<LocalOrdinal,GlobalOrdinal,Node>&
00616       operator= (const CrsGraph<LocalOrdinal,GlobalOrdinal,Node> &rhs);
00617 
00618     protected:
00619       typedef typename LocalMatOps::template graph<LocalOrdinal,Node>::graph_type local_graph_type;
00620 
00621       // these structs are conveniences, to cut down on the number of
00622       // arguments to some of the methods below.
00623       struct SLocalGlobalViews {
00624         ArrayView<const GlobalOrdinal> ginds;
00625         ArrayView<const LocalOrdinal>  linds;
00626       };
00627       struct SLocalGlobalNCViews {
00628         ArrayView<GlobalOrdinal>       ginds;
00629         ArrayView<LocalOrdinal>        linds;
00630       };
00631       //
00632       // Allocation
00633       //
00634       bool indicesAreAllocated() const;
00635 
00636       void allocateIndices (ELocalGlobal lg);
00637 
00638       template <class T>
00639       ArrayRCP<T> allocateValues1D () const;
00640       template <class T>
00641       ArrayRCP<ArrayRCP<T> > allocateValues2D () const;
00642 
00643       template <ELocalGlobal lg>
00644       RowInfo updateAlloc (RowInfo rowinfo, size_t allocSize);
00645       template <ELocalGlobal lg, class T>
00646       RowInfo updateAllocAndValues (RowInfo rowinfo, size_t allocSize, ArrayRCP<T> &rowVals);
00647       //
00648       // Local versus global indices
00649       //
00650       void computeIndexState();
00651       void makeColMap();
00652       void makeIndicesLocal();
00653       void makeImportExport();
00654       //
00655       // insert/suminto/replace
00656       //
00657       template<ELocalGlobal lg>
00658       size_t filterIndices (const SLocalGlobalNCViews &inds) const;
00659 
00660       template<ELocalGlobal lg, class T>
00661       size_t filterIndicesAndValues (const SLocalGlobalNCViews &inds, const ArrayView<T> &vals) const;
00662 
00663       template<ELocalGlobal lg, ELocalGlobal I>
00664       size_t insertIndices (RowInfo rowInfo, const SLocalGlobalViews &newInds);
00665 
00666       template<ELocalGlobal lg, ELocalGlobal I, class IterO, class IterN>
00667       void insertIndicesAndValues (RowInfo rowInfo, const SLocalGlobalViews &newInds, IterO rowVals, IterN newVals);
00668 
00669       template<ELocalGlobal lg, class IterO, class IterN, class BinaryFunction>
00670       void transformValues (RowInfo rowInfo, const SLocalGlobalViews &inds, IterO rowVals, IterN newVals, BinaryFunction f) const;
00671       //
00672       // Sorting and merging
00673       //
00674       bool                       isMerged() const;
00675       void                       setSorted(bool sorted);
00676       void                       setMerged(bool merged);
00677       void                       sortAllIndices();
00678       void                       sortRowIndices(RowInfo rowinfo);
00679       template <class Scalar> void sortRowIndicesAndValues(RowInfo rowinfo, ArrayView<Scalar> values);
00680       void                                             mergeAllIndices();
00681       void                                             mergeRowIndices(RowInfo rowinfo);
00682       template <class Iter, class BinaryFunction> void mergeRowIndicesAndValues(RowInfo rowinfo, Iter rowValueIter, BinaryFunction f);
00683       //
00684       void setDomainRangeMaps(const RCP<const Map<LocalOrdinal,GlobalOrdinal,Node> > &domainMap, const RCP<const Map<LocalOrdinal,GlobalOrdinal,Node> > &rangeMap);
00685       void staticAssertions() const;
00686       // global consts
00687       void clearGlobalConstants();
00688       void computeGlobalConstants();
00689       // graph data accessors
00690       RowInfo                         getRowInfo(size_t myRow) const;
00691       ArrayView<const LocalOrdinal>   getLocalView(RowInfo rowinfo) const;
00692       ArrayView<LocalOrdinal>         getLocalViewNonConst(RowInfo rowinfo);
00693       ArrayView<const GlobalOrdinal>  getGlobalView(RowInfo rowinfo) const;
00694       ArrayView<GlobalOrdinal>        getGlobalViewNonConst(RowInfo rowinfo);
00695       size_t                          findLocalIndex(RowInfo rowinfo, LocalOrdinal ind) const;
00696       size_t                          findGlobalIndex(RowInfo rowinfo, GlobalOrdinal ind) const;
00697       // local Kokkos objects
00698       void fillLocalGraph(const RCP<ParameterList> &params);
00699       const RCP<const local_graph_type> getLocalGraph() const;
00700       const RCP<local_graph_type> getLocalGraphNonConst();
00701       // debugging
00702       void checkInternalState() const;
00703 
00704       // Tpetra support objects
00705       RCP<const Map<LocalOrdinal,GlobalOrdinal,Node> > rowMap_, colMap_, rangeMap_, domainMap_;
00706       RCP<Import<LocalOrdinal,GlobalOrdinal,Node> > importer_;
00707       RCP<Export<LocalOrdinal,GlobalOrdinal,Node> > exporter_;
00708 
00709       // local data, stored in a Kokkos::CrsGraph. only initialized after fillComplete()
00710       RCP<local_graph_type> lclGraph_;
00711 
00712       // Local and Global Counts
00713       // nodeNumEntries_ and nodeNumAllocated_ are required to be always consistent
00714       // nodeMaxNumEntries_, nodeNumDiags_ and the global quantities are computed during fillComplete() and only valid when isFillComplete()
00715       global_size_t globalNumEntries_, globalNumDiags_, globalMaxNumRowEntries_;
00716       size_t          nodeNumEntries_,   nodeNumDiags_,   nodeMaxNumRowEntries_, nodeNumAllocated_;
00717 
00718       // allocate static or dynamic?
00719       ProfileType pftype_;
00720       // requested allocation sizes; we have to preserve these, because we perform late-allocation
00721       // number of non-zeros to allocate per row; set to null after they are allocated.
00722       ArrayRCP<const size_t> numAllocPerRow_;
00723       // number of non-zeros to allocate for all row; either this or numAllocPerRow_ is used, but not both.
00724       size_t numAllocForAllRows_;
00725 
00726       // graph indices. before allocation, all are null.
00727       // after allocation, except during makeIndicesLocal(), one of local or global is null.
00728       // we will never have 1D and 2D structures being non-null
00729       // this is host memory
00730       // 1D == StaticAllocation, 2D == DynamicAllocation
00732       //
00733       // 1D/Static structures
00734       //
00737       ArrayRCP< LocalOrdinal>                     lclInds1D_;
00739       ArrayRCP<GlobalOrdinal>                     gblInds1D_;
00740       // offset to the beg entries of each row. only used for 1D (Static) allocation.
00741       // i.e., indices for row R are lclInds1D_[i] for i in [b,e) where b = rowPtrs_[R] and e = rowPtrs_[R+1]
00742       // only the first numRowEntries_[R] of these are valid
00743       // both of these are null for 2D (Dynamic) allocations
00744       // rowPtrs_ has length N+1, while numRowEntries_ has length N
00745       // we may delete this to save memory on fillComplete, if "Delete Row Pointers" is speified
00746       ArrayRCP<size_t> rowPtrs_;
00748       //
00749       // 2D/Dynamic structures.
00750       //
00753       ArrayRCP<ArrayRCP< LocalOrdinal> > lclInds2D_;
00755       ArrayRCP<ArrayRCP<GlobalOrdinal> > gblInds2D_;
00756 
00758       // This is deleted after fillCOmplete if "Optimize Storage" is set to \c true
00759       ArrayRCP<size_t>       numRowEntries_;
00760 
00761       bool indicesAreAllocated_,
00762            indicesAreLocal_,
00763            indicesAreGlobal_,
00764            fillComplete_,
00765            lowerTriangular_,
00766            upperTriangular_,
00767            indicesAreSorted_,
00768            noRedundancies_,
00769            haveGlobalConstants_;
00770 
00771       // non-local data
00772       std::map<GlobalOrdinal, std::deque<GlobalOrdinal> > nonlocals_;
00773 
00774       bool haveRowInfo_;
00775       inline bool                     hasRowInfo() const {
00776 #ifdef HAVE_TPETRA_DEBUG
00777         bool actuallyHasRowInfo = true;
00778         if (indicesAreAllocated() && getProfileType() == StaticProfile && rowPtrs_ == null) actuallyHasRowInfo = false;
00779         TEUCHOS_TEST_FOR_EXCEPTION(
00780             actuallyHasRowInfo != haveRowInfo_,
00781             std::logic_error, "Internal logic error. Please contact Tpetra team."
00782         )
00783 #endif
00784         return haveRowInfo_;
00785       }
00786 
00788     bool insertGlobalIndicesWarnedEfficiency_;
00790     bool insertLocalIndicesWarnedEfficiency_;
00791 
00792   }; // class CrsGraph
00793 
00794 } // namespace Tpetra
00795 
00796 #endif
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines