AssemblyTree.h

Go to the documentation of this file.

// ========================================================================= //
// This file is part of MyraMath, copyright (c) 2014-2019 by Ryan A Chilton  //
// and distributed by MyraCore, LLC. See LICENSE.txt for license terms.      //
// ========================================================================= //

#ifndef MYRAMATH_MULTIFRONTAL_SYMBOLIC_ASSEMBLYTREE_H
#define MYRAMATH_MULTIFRONTAL_SYMBOLIC_ASSEMBLYTREE_H

#include <myramath/MYRAMATH_EXPORT.h>
#include <myramath/utility/Array1.h>
#include <myramath/utility/Array2.h>

#include <myramath/sparse/Permutation.h>

#include <myramath/multifrontal/Options.h>

// Required std::libraries.
#include <vector>
#include <iosfwd>
#include <stdint.h>

namespace myra {

// Forward declarations.
class intCRange;
class Match;
class PatternRange;
class InputStream;
class OutputStream;
class SchurTree;

class MYRAMATH_EXPORT AssemblyTree
  {
  public:

    typedef std::pair<const int*,const int*> Range;
    typedef multifrontal::Options Options;

    // Inner class detail, single Node of the AssemblyTree
    class MYRAMATH_EXPORT Node
      {
      public:
        
        // Unique identifier for this node.
        int id;

        // Number of pivots (p) and nonpivots (q)
        int p;
        int q;
        std::vector<int> pattern;

        // Number of pivot blocks (P) and nonpivot blocks (Q)
        int P;
        int Q;
        std::vector<int> blocking;

        // Striding vector, cumsum(blocking)
        std::vector<int> striding;

        // Parent/child links.
        Node* parent;
        std::vector<Node*> children;

        // Default constructor, empty Node
        Node();

        // InputStream constructor.
        Node(InputStream& in);

        // Writes to OutputStream. 
        void write(OutputStream& out);

        // Returns id of parent (or -1 if *this is a root)
        int parent_id() const;

        // Returns id's of all children.
        std::vector<int> children_ids() const;

            // Inspection routine, prints debugging information on out.
            void inspect(std::ostream& out) const;

        // ------------------------------------ Pattern interrogation.
        
        // Returns pattern of pivots.
        Range p_pattern() const
          { return Range(pattern.data(), pattern.data()+p); }

        // Returns pattern of nonpivots.
        Range q_pattern() const
          { return Range(pattern.data()+p, pattern.data()+p+q); }

        // Returns blocking of pivots.
        Range p_blocking() const
          { return Range(blocking.data(), blocking.data()+P); }

        // Returns blocking of nonpivots.
        Range q_blocking() const
          { return Range(blocking.data()+P, blocking.data()+P+Q); }
        
        // Returns pattern of block b, for b in [0,P+Q]
        Range block_pattern(int b) const
          { return Range(pattern.data()+striding[b], pattern.data()+striding[b+1]); }

        // ------------------------------------ Space/time queries.

        // Returns (permanent,temporary) storage requirements.
        std::pair<uint64_t,uint64_t> n_words() const;

        // Returns work estimate to process this node.
        uint64_t n_work_llt() const;
        uint64_t n_work_lu() const;

        // ------------------------------------ Dependency tracking

        // Given a contribution block b in [P,P+Q], returns the set of (parent,block)'s that it pushes contributions into.
        Range block_up(int b) const;

        // Given a block b, returns the set of children[c] blocks it pulls contributions from.
        Range block_down(int b, int c) const;

      private:
      
        // Caches the child to parent relationships, exposed by block_up()
        std::vector<int> up_data;
        Array1<int> up_begin;
        Array1<int> up_end;
        
        // Caches the parent to child relationships, exposed by block_down()
        std::vector<int> down_data;
        Array2<int> down_begin;
        Array2<int> down_end;

        // Populates the caches above.
        void finalize(int blocksize);

        // Given a contribution block b in [P,P+Q], returns the set of (parent,block)'s that it pushes contributions into.
        // Implementation detail of finalize()
        std::vector<int> block_up_finalize(int b, int blocksize) const;

        // Given a block b, returns the set of children[c] blocks it pulls contributions from.
        // Implementation detail of finalize()
        std::vector<int> block_down_finalize(int b, int c, int blocksize) const;

        // Given a sorted range of indices, finds the match for each one in this->pattern. (or -1, if !found)
        // Implementation detail of block_up_finalize() and block_down_finalize()
        std::vector<int> map(Range range) const;

        friend class AssemblyTree;
        
      }; // class Node

    AssemblyTree();
    
    AssemblyTree(const PatternRange& A, const Permutation& P, Options options = Options::create());

    AssemblyTree(const PatternRange& A, const Match& M, const Permutation& P, Options options = Options::create());

    AssemblyTree(const AssemblyTree& that);

    AssemblyTree(InputStream& in);

    void write(OutputStream& out) const;

    void swap(AssemblyTree& that);

#ifdef MYRAMATH_ENABLE_CPP11
    AssemblyTree(AssemblyTree&& that);
#endif

    AssemblyTree& operator = (AssemblyTree that);

    int size() const;

    int n_nodes() const;

    const Node& node(int n) const;
    const Node& at(int n) const;    

    int unknown2node(int i) const;

    std::vector<int> roots() const;
    
    std::vector<int> leaves() const;

    // High water mark should be approximately the sum of .first + .second
    std::pair<uint64_t,uint64_t> n_words() const;

    uint64_t n_work_llt() const;

    uint64_t n_work_lu() const;

    const Permutation& permutation() const;
    intCRange perm() const;
    intCRange iperm() const;
    intCRange swaps() const;
    int perm(int i) const;
    int iperm(int i) const;
    int swaps(int i) const;

    void inspect(std::ostream& out) const;

   ~AssemblyTree();

  private:

    // Implementation detail of constructor, performs symbolic analysis.
    void constructor_detail(const PatternRange& A, const Match& match, const Permutation& perm, Options options);    

    // Internal contents.
    std::vector<Node*> nodes;

    // Size of underlying system.
    int IJ;

    // Internal permutation stage.
    Permutation P;

    // Maps pivot unknowns to AssemblyTree::Node's that eliminate them.
    std::vector<int> pivot2node;

    // Blocksize, required for SchurTree constructor.
    int blocksize;
    friend class SchurTree;

  };

std::ostream& operator<< (std::ostream& out, const AssemblyTree& atree);

} // namespace myra

#endif