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 
00598       ArrayRCP<const size_t> getNodeRowPtrs() const;
00599 
00601 
00603       ArrayRCP<const LocalOrdinal> getNodePackedIndices() const;
00604 
00606 
00608 
00609 
00618       TPETRA_DEPRECATED void optimizeStorage();
00619 
00621       TPETRA_DEPRECATED ArrayRCP<const GlobalOrdinal> getGlobalRowView(GlobalOrdinal GlobalRow) const;
00622 
00624       TPETRA_DEPRECATED ArrayRCP<const LocalOrdinal> getLocalRowView(LocalOrdinal LocalRow) const;
00625 
00627       TPETRA_DEPRECATED void fillComplete(const RCP<const Map<LocalOrdinal,GlobalOrdinal,Node> > &domainMap, const RCP<const Map<LocalOrdinal,GlobalOrdinal,Node> > &rangeMap, OptimizeOption os);
00628 
00630       TPETRA_DEPRECATED void fillComplete(OptimizeOption os);
00631 
00633 
00634     private:
00635       // We forbid copy construction by declaring this method private
00636       // and not implementing it.
00637       CrsGraph (const CrsGraph<LocalOrdinal,GlobalOrdinal,Node> &Source);
00638 
00639       // We forbid assignment (operator=) by declaring this method
00640       // private and not implementing it.
00641       CrsGraph<LocalOrdinal,GlobalOrdinal,Node>& 
00642       operator= (const CrsGraph<LocalOrdinal,GlobalOrdinal,Node> &rhs);
00643 
00644     protected:
00645       typedef typename LocalMatOps::template graph<LocalOrdinal,Node>::graph_type local_graph_type;
00646       
00647       // these structs are conveniences, to cut down on the number of
00648       // arguments to some of the methods below.
00649       struct SLocalGlobalViews {
00650         ArrayView<const GlobalOrdinal> ginds;
00651         ArrayView<const LocalOrdinal>  linds;
00652       };
00653       struct SLocalGlobalNCViews {
00654         ArrayView<GlobalOrdinal>       ginds;
00655         ArrayView<LocalOrdinal>        linds;
00656       };
00657       //
00658       // Allocation
00659       //
00660       bool indicesAreAllocated() const;
00661 
00662       void allocateIndices (ELocalGlobal lg);
00663 
00664       template <class T>
00665       ArrayRCP<T> allocateValues1D () const;
00666       template <class T>
00667       ArrayRCP<ArrayRCP<T> > allocateValues2D () const;
00668 
00669       template <ELocalGlobal lg>
00670       RowInfo updateAlloc (RowInfo rowinfo, size_t allocSize);
00671       template <ELocalGlobal lg, class T> 
00672       RowInfo updateAllocAndValues (RowInfo rowinfo, size_t allocSize, ArrayRCP<T> &rowVals);
00673       //
00674       // Local versus global indices
00675       //
00676       void computeIndexState();
00677       void makeColMap();
00678       void makeIndicesLocal();
00679       void makeImportExport();
00680       //
00681       // insert/suminto/replace
00682       //
00683       template<ELocalGlobal lg>
00684       size_t filterIndices (const SLocalGlobalNCViews &inds) const;
00685 
00686       template<ELocalGlobal lg, class T>
00687       size_t filterIndicesAndValues (const SLocalGlobalNCViews &inds, const ArrayView<T> &vals) const;
00688 
00689       template<ELocalGlobal lg, ELocalGlobal I> 
00690       size_t insertIndices (RowInfo rowInfo, const SLocalGlobalViews &newInds);
00691 
00692       template<ELocalGlobal lg, ELocalGlobal I, class IterO, class IterN> 
00693       void insertIndicesAndValues (RowInfo rowInfo, const SLocalGlobalViews &newInds, IterO rowVals, IterN newVals);
00694 
00695       template<ELocalGlobal lg, class IterO, class IterN, class BinaryFunction> 
00696       void transformValues (RowInfo rowInfo, const SLocalGlobalViews &inds, IterO rowVals, IterN newVals, BinaryFunction f) const;
00697       //
00698       // Sorting and merging
00699       //
00700       bool                       isMerged() const;
00701       void                       setSorted(bool sorted);
00702       void                       setMerged(bool merged);
00703       void                       sortAllIndices();
00704       void                       sortRowIndices(RowInfo rowinfo);
00705       template <class Scalar> void sortRowIndicesAndValues(RowInfo rowinfo, ArrayView<Scalar> values);
00706       void                                             mergeAllIndices();
00707       void                                             mergeRowIndices(RowInfo rowinfo);
00708       template <class Iter, class BinaryFunction> void mergeRowIndicesAndValues(RowInfo rowinfo, Iter rowValueIter, BinaryFunction f);
00709       // 
00710       void setDomainRangeMaps(const RCP<const Map<LocalOrdinal,GlobalOrdinal,Node> > &domainMap, const RCP<const Map<LocalOrdinal,GlobalOrdinal,Node> > &rangeMap);
00711       void staticAssertions() const;
00712       // global consts
00713       void clearGlobalConstants();
00714       void computeGlobalConstants();
00715       // graph data accessors
00716       RowInfo                         getRowInfo(size_t myRow) const;
00717       ArrayView<const LocalOrdinal>   getLocalView(RowInfo rowinfo) const;
00718       ArrayView<LocalOrdinal>         getLocalViewNonConst(RowInfo rowinfo);
00719       ArrayView<const GlobalOrdinal>  getGlobalView(RowInfo rowinfo) const;
00720       ArrayView<GlobalOrdinal>        getGlobalViewNonConst(RowInfo rowinfo);
00721       size_t                          findLocalIndex(RowInfo rowinfo, LocalOrdinal ind) const;
00722       size_t                          findGlobalIndex(RowInfo rowinfo, GlobalOrdinal ind) const;
00723       // local Kokkos objects
00724       void fillLocalGraph(const RCP<ParameterList> &params);
00725       const RCP<const local_graph_type> getLocalGraph() const;
00726       const RCP<local_graph_type> getLocalGraphNonConst();
00727       // debugging
00728       void checkInternalState() const;
00729 
00730       // Tpetra support objects
00731       RCP<const Map<LocalOrdinal,GlobalOrdinal,Node> > rowMap_, colMap_, rangeMap_, domainMap_;
00732       RCP<Import<LocalOrdinal,GlobalOrdinal,Node> > importer_;
00733       RCP<Export<LocalOrdinal,GlobalOrdinal,Node> > exporter_;
00734 
00735       // local data, stored in a Kokkos::CrsGraph. only initialized after fillComplete()
00736       RCP<local_graph_type> lclGraph_;
00737 
00738       // Local and Global Counts
00739       // nodeNumEntries_ and nodeNumAllocated_ are required to be always consistent
00740       // nodeMaxNumEntries_, nodeNumDiags_ and the global quantities are computed during fillComplete() and only valid when isFillComplete()
00741       global_size_t globalNumEntries_, globalNumDiags_, globalMaxNumRowEntries_;
00742       size_t          nodeNumEntries_,   nodeNumDiags_,   nodeMaxNumRowEntries_, nodeNumAllocated_;
00743 
00744       // allocate static or dynamic?
00745       ProfileType pftype_;
00746       // requested allocation sizes; we have to preserve these, because we perform late-allocation
00747       // number of non-zeros to allocate per row; set to null after they are allocated.
00748       ArrayRCP<const size_t> numAllocPerRow_;
00749       // number of non-zeros to allocate for all row; either this or numAllocPerRow_ is used, but not both.
00750       size_t numAllocForAllRows_;
00751 
00752       // graph indices. before allocation, all are null. 
00753       // after allocation, except during makeIndicesLocal(), one of local or global is null.
00754       // we will never have 1D and 2D structures being non-null
00755       // this is host memory
00756       // 1D == StaticAllocation, 2D == DynamicAllocation
00758       //
00759       // 1D/Static structures
00760       //
00763       ArrayRCP< LocalOrdinal>                     lclInds1D_;
00765       ArrayRCP<GlobalOrdinal>                     gblInds1D_;
00766       // offset to the beg entries of each row. only used for 1D (Static) allocation.
00767       // i.e., indices for row R are lclInds1D_[i] for i in [b,e) where b = rowPtrs_[R] and e = rowPtrs_[R+1]
00768       // only the first numRowEntries_[R] of these are valid
00769       // both of these are null for 2D (Dynamic) allocations
00770       // rowPtrs_ has length N+1, while numRowEntries_ has length N
00771       // TODO: it is possible that making these size_t is overkill; revisit
00772       ArrayRCP<size_t> rowPtrs_;
00774       //
00775       // 2D/Dynamic structures. 
00776       //
00779       ArrayRCP<ArrayRCP< LocalOrdinal> > lclInds2D_;
00781       ArrayRCP<ArrayRCP<GlobalOrdinal> > gblInds2D_;
00782 
00784       ArrayRCP<size_t>       numRowEntries_;
00785 
00786       // TODO: these might be useful in the future
00787       // ArrayRCP< typedef ArrayRCP<const GlobalOrdinal>::iterator > gRowPtrs_;
00788       // ArrayRCP< typedef ArrayRCP<GlobalOrdinal>::iterator > gRowPtrsNC_;
00789       // ArrayRCP< typedef ArrayRCP<const LocalOrdinal>::iterator > lRowPtrs_;
00790       // ArrayRCP< typedef ArrayRCP<LocalOrdinal>::iterator > lRowPtrsNC_;
00791 
00792       bool indicesAreAllocated_,
00793            indicesAreLocal_,
00794            indicesAreGlobal_,
00795            fillComplete_, 
00796            lowerTriangular_,
00797            upperTriangular_,
00798            indicesAreSorted_,
00799            noRedundancies_,
00800            haveGlobalConstants_;
00801 
00802       // non-local data
00803       std::map<GlobalOrdinal, std::deque<GlobalOrdinal> > nonlocals_;
00804 
00805   }; // class CrsGraph
00806 
00807 } // namespace Tpetra
00808 
00809 #endif
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines