HSSMatrixBase.hpp
Go to the documentation of this file.
1 /*
2  * STRUMPACK -- STRUctured Matrices PACKage, Copyright (c) 2014, The
3  * Regents of the University of California, through Lawrence Berkeley
4  * National Laboratory (subject to receipt of any required approvals
5  * from the U.S. Dept. of Energy). All rights reserved.
6  *
7  * If you have questions about your rights to use or distribute this
8  * software, please contact Berkeley Lab's Technology Transfer
9  * Department at TTD@lbl.gov.
10  *
11  * NOTICE. This software is owned by the U.S. Department of Energy. As
12  * such, the U.S. Government has been granted for itself and others
13  * acting on its behalf a paid-up, nonexclusive, irrevocable,
14  * worldwide license in the Software to reproduce, prepare derivative
15  * works, and perform publicly and display publicly. Beginning five
16  * (5) years after the date permission to assert copyright is obtained
17  * from the U.S. Department of Energy, and subject to any subsequent
18  * five (5) year renewals, the U.S. Government is granted for itself
19  * and others acting on its behalf a paid-up, nonexclusive,
20  * irrevocable, worldwide license in the Software to reproduce,
21  * prepare derivative works, distribute copies to the public, perform
22  * publicly and display publicly, and to permit others to do so.
23  *
24  * Developers: Pieter Ghysels, Francois-Henry Rouet, Xiaoye S. Li.
25  * (Lawrence Berkeley National Lab, Computational Research
26  * Division).
27  *
28  */
34 #ifndef HSS_MATRIX_BASE_HPP
35 #define HSS_MATRIX_BASE_HPP
36 
37 #include <cassert>
38 #include <iostream>
39 #include <vector>
40 #include <functional>
41 
42 #include "dense/DenseMatrix.hpp"
43 #include "misc/Triplet.hpp"
44 #include "HSSOptions.hpp"
45 #include "HSSExtra.hpp"
46 #if defined(STRUMPACK_USE_MPI)
47 #include "dense/DistributedMatrix.hpp"
48 #include "HSSExtraMPI.hpp"
49 #include "HSSMatrixMPI.hpp"
50 #endif
51 
52 namespace strumpack {
53  namespace HSS {
54 
55 #ifndef DOXYGEN_SHOULD_SKIP_THIS
56  template<typename scalar_t> class HSSMatrix;
57 #if defined(STRUMPACK_USE_MPI)
58  template<typename scalar_t> class HSSMatrixMPI;
59  template<typename scalar_t> class DistSubLeaf;
60  template<typename scalar_t> class DistSamples;
61 #endif //defined(STRUMPACK_USE_MPI)
62 #endif //DOXYGEN_SHOULD_SKIP_THIS
63 
64 
79  template<typename scalar_t> class HSSMatrixBase {
80  using real_t = typename RealType<scalar_t>::value_type;
81  using DenseM_t = DenseMatrix<scalar_t>;
82  using DenseMW_t = DenseMatrixWrapper<scalar_t>;
83  using elem_t = typename std::function
84  <void(const std::vector<std::size_t>& I,
85  const std::vector<std::size_t>& J, DenseM_t& B)>;
86  using opts_t = HSSOptions<scalar_t>;
87 #if defined(STRUMPACK_USE_MPI)
88  using DistM_t = DistributedMatrix<scalar_t>;
89  using DistMW_t = DistributedMatrixWrapper<scalar_t>;
90  using delem_t = typename std::function
91  <void(const std::vector<std::size_t>& I,
92  const std::vector<std::size_t>& J, DistM_t& B)>;
93 #endif //defined(STRUMPACK_USE_MPI)
94 
95  public:
104  HSSMatrixBase(std::size_t m, std::size_t n, bool active);
105 
109  virtual ~HSSMatrixBase() = default;
110 
115  HSSMatrixBase(const HSSMatrixBase<scalar_t>& other);
116 
122  HSSMatrixBase<scalar_t>& operator=(const HSSMatrixBase<scalar_t>& other);
123 
128  HSSMatrixBase(HSSMatrixBase&& h) = default;
129 
135  HSSMatrixBase& operator=(HSSMatrixBase&& h) = default;
136 
143  virtual std::unique_ptr<HSSMatrixBase<scalar_t>> clone() const = 0;
144 
151  std::pair<std::size_t,std::size_t> dims() const {
152  return std::make_pair(_rows, _cols);
153  }
154 
159  std::size_t rows() const { return _rows; }
160 
165  std::size_t cols() const { return _cols; }
166 
171  bool leaf() const { return _ch.empty(); }
172 
182  const HSSMatrixBase<scalar_t>& child(int c) const {
183  assert(c>=0 && c<int(_ch.size())); return *(_ch[c]);
184  }
185 
195  HSSMatrixBase<scalar_t>& child(int c) {
196  assert(c>=0 && c<int(_ch.size())); return *(_ch[c]);
197  }
198 
207  bool is_compressed() const {
208  return _U_state == State::COMPRESSED &&
209  _V_state == State::COMPRESSED;
210  }
211 
222  bool is_untouched() const {
223  return _U_state == State::UNTOUCHED &&
224  _V_state == State::UNTOUCHED;
225  }
226 
233  bool active() const { return _active; };
234 
241  virtual std::size_t rank() const = 0;
242 
251  virtual std::size_t memory() const = 0;
252 
260  virtual std::size_t nonzeros() const = 0;
261 
267  virtual std::size_t levels() const = 0;
268 
281  virtual void print_info
282  (std::ostream &out=std::cout,
283  std::size_t roff=0, std::size_t coff=0) const = 0;
284 
294  void set_openmp_task_depth(int depth) { _openmp_task_depth = depth; }
295 
296 #ifndef DOXYGEN_SHOULD_SKIP_THIS
297  virtual void delete_trailing_block() { if (_ch.size()==2) _ch.resize(1); }
298  virtual void reset() {
299  _U_state = _V_state = State::UNTOUCHED;
300  _U_rank = _U_rows = _V_rank = _V_rows = 0;
301  for (auto& c : _ch) c->reset();
302  }
303 #endif
304 
312  virtual void shift(scalar_t sigma) = 0;
313 
320  virtual void draw
321  (std::ostream& of, std::size_t rlo, std::size_t clo) const {};
322 
323 #if defined(STRUMPACK_USE_MPI)
324  virtual void forward_solve
325  (const HSSFactorsMPI<scalar_t>& ULV, WorkSolveMPI<scalar_t>& w,
326  const DistM_t& b, bool partial) const;
327  virtual void backward_solve
328  (const HSSFactorsMPI<scalar_t>& ULV, WorkSolveMPI<scalar_t>& w,
329  DistM_t& x) const;
330 
331  virtual const BLACSGrid* grid() const { return nullptr; }
332  virtual const BLACSGrid* grid(const BLACSGrid* local_grid) const {
333  return active() ? local_grid : nullptr;
334  }
335  virtual const BLACSGrid* grid_local() const { return nullptr; }
336  virtual int Ptotal() const { return 1; }
337  virtual int Pactive() const { return 1; }
338 
339  virtual void to_block_row
340  (const DistM_t& A, DenseM_t& sub_A, DistM_t& leaf_A) const;
341  virtual void allocate_block_row
342  (int d, DenseM_t& sub_A, DistM_t& leaf_A) const;
343  virtual void from_block_row
344  (DistM_t& A, const DenseM_t& sub_A, const DistM_t& leaf_A,
345  const BLACSGrid* lg) const;
346 #endif //defined(STRUMPACK_USE_MPI)
347 
348  protected:
349  std::size_t _rows, _cols;
350 
351  // TODO store children array in the sub-class???
352  std::vector<std::unique_ptr<HSSMatrixBase<scalar_t>>> _ch;
353  State _U_state, _V_state;
354  int _openmp_task_depth;
355  bool _active;
356 
357  int _U_rank = 0, _U_rows = 0, _V_rank = 0, _V_rows = 0;
358  virtual std::size_t U_rank() const { return _U_rank; }
359  virtual std::size_t V_rank() const { return _V_rank; }
360  virtual std::size_t U_rows() const { return _U_rows; };
361  virtual std::size_t V_rows() const { return _V_rows; };
362 
363  // Used to redistribute the original 2D block cyclic matrix
364  // according to the HSS tree
365  DenseM_t _Asub;
366 
367  virtual void compress_recursive_original
368  (DenseM_t& Rr, DenseM_t& Rc, DenseM_t& Sr, DenseM_t& Sc,
369  const elem_t& Aelem, const opts_t& opts, WorkCompress<scalar_t>& w,
370  int dd, int depth) {};
371  virtual void compress_recursive_stable
372  (DenseM_t& Rr, DenseM_t& Rc, DenseM_t& Sr, DenseM_t& Sc,
373  const elem_t& Aelem, const opts_t& opts, WorkCompress<scalar_t>& w,
374  int d, int dd, int depth) {};
375  virtual void compress_level_original
376  (DenseM_t& Rr, DenseM_t& Rc, DenseM_t& Sr, DenseM_t& Sc,
377  const opts_t& opts, WorkCompress<scalar_t>& w,
378  int dd, int lvl, int depth) {}
379  virtual void compress_level_stable
380  (DenseM_t& Rr, DenseM_t& Rc, DenseM_t& Sr, DenseM_t& Sc,
381  const opts_t& opts, WorkCompress<scalar_t>& w,
382  int d, int dd, int lvl, int depth) {}
383  virtual void compress_recursive_ann
384  (DenseMatrix<std::uint32_t>& ann, DenseMatrix<real_t>& scores,
385  const elem_t& Aelem, const opts_t& opts,
386  WorkCompressANN<scalar_t>& w, int depth) {}
387 
388  virtual void get_extraction_indices
389  (std::vector<std::vector<std::size_t>>& I,
390  std::vector<std::vector<std::size_t>>& J,
391  const std::pair<std::size_t,std::size_t>& off,
392  WorkCompress<scalar_t>& w, int& self, int lvl) {}
393 
394  virtual void get_extraction_indices
395  (std::vector<std::vector<std::size_t>>& I,
396  std::vector<std::vector<std::size_t>>& J,
397  std::vector<DenseM_t*>& B,
398  const std::pair<std::size_t,std::size_t>& off,
399  WorkCompress<scalar_t>& w, int& self, int lvl) {}
400  virtual void extract_D_B
401  (const elem_t& Aelem, const opts_t& opts,
402  WorkCompress<scalar_t>& w, int lvl) {}
403 
404  virtual real_t update_orthogonal_basis
405  (DenseM_t& S, int d, int dd, int depth) { return real_t(0.); }
406 
407  virtual void factor_recursive
408  (HSSFactors<scalar_t>& ULV, WorkFactor<scalar_t>& w,
409  bool isroot, bool partial, int depth) const {};
410 
411  virtual void apply_fwd
412  (const DenseM_t& b, WorkApply<scalar_t>& w,
413  bool isroot, int depth, std::atomic<long long int>& flops) const {};
414  virtual void apply_bwd
415  (const DenseM_t& b, scalar_t beta, DenseM_t& c, WorkApply<scalar_t>& w,
416  bool isroot, int depth, std::atomic<long long int>& flops) const {};
417  virtual void applyT_fwd
418  (const DenseM_t& b, WorkApply<scalar_t>& w, bool isroot,
419  int depth, std::atomic<long long int>& flops) const {};
420  virtual void applyT_bwd
421  (const DenseM_t& b, scalar_t beta, DenseM_t& c, WorkApply<scalar_t>& w,
422  bool isroot, int depth, std::atomic<long long int>& flops) const {};
423 
424  virtual void forward_solve
425  (const HSSFactors<scalar_t>& ULV, WorkSolve<scalar_t>& w,
426  const DenseMatrix<scalar_t>& b, bool partial) const {};
427  virtual void backward_solve
428  (const HSSFactors<scalar_t>& ULV, WorkSolve<scalar_t>& w,
429  DenseMatrix<scalar_t>& b) const {};
430  virtual void solve_fwd
431  (const HSSFactors<scalar_t>& ULV, const DenseM_t& b,
432  WorkSolve<scalar_t>& w, bool partial, bool isroot, int depth) const {};
433  virtual void solve_bwd
434  (const HSSFactors<scalar_t>& ULV, DenseM_t& x, WorkSolve<scalar_t>& w,
435  bool isroot, int depth) const {};
436 
437  virtual void extract_fwd
438  (WorkExtract<scalar_t>& w, bool odiag, int depth) const {};
439  virtual void extract_bwd
440  (DenseMatrix<scalar_t>& B, WorkExtract<scalar_t>& w,
441  int depth) const {};
442  virtual void extract_bwd
443  (std::vector<Triplet<scalar_t>>& triplets,
444  WorkExtract<scalar_t>& w, int depth) const {};
445 
446  virtual void apply_UV_big
447  (DenseM_t& Theta, DenseM_t& Uop, DenseM_t& Phi, DenseM_t& Vop,
448  const std::pair<std::size_t, std::size_t>& offset, int depth,
449  std::atomic<long long int>& flops) const {};
450  virtual void apply_UtVt_big
451  (const DenseM_t& A, DenseM_t& UtA, DenseM_t& VtA,
452  const std::pair<std::size_t, std::size_t>& offset,
453  int depth, std::atomic<long long int>& flops) const {};
454 
455  virtual void dense_recursive
456  (DenseM_t& A, WorkDense<scalar_t>& w, bool isroot, int depth) const {};
457 
458  friend class HSSMatrix<scalar_t>;
459 
460 #if defined(STRUMPACK_USE_MPI)
461  using delemw_t = typename std::function
462  <void(const std::vector<std::size_t>& I,
463  const std::vector<std::size_t>& J,
464  DistM_t& B, DistM_t& A,
465  std::size_t rlo, std::size_t clo,
466  MPI_Comm comm)>;
467 
468  virtual void compress_recursive_original
469  (DistSamples<scalar_t>& RS, const delemw_t& Aelem,
470  const opts_t& opts, WorkCompressMPI<scalar_t>& w, int dd);
471  virtual void compress_recursive_stable
472  (DistSamples<scalar_t>& RS, const delemw_t& Aelem,
473  const opts_t& opts, WorkCompressMPI<scalar_t>& w, int d, int dd);
474  virtual void compress_level_original
475  (DistSamples<scalar_t>& RS, const opts_t& opts,
476  WorkCompressMPI<scalar_t>& w, int dd, int lvl);
477  virtual void compress_level_stable
478  (DistSamples<scalar_t>& RS, const opts_t& opts,
479  WorkCompressMPI<scalar_t>& w, int d, int dd, int lvl);
480  virtual void compress_recursive_ann
481  (DenseMatrix<std::uint32_t>& ann, DenseMatrix<real_t>& scores,
482  const delemw_t& Aelem, WorkCompressMPIANN<scalar_t>& w,
483  const opts_t& opts, const BLACSGrid* lg);
484 
485  virtual void get_extraction_indices
486  (std::vector<std::vector<std::size_t>>& I,
487  std::vector<std::vector<std::size_t>>& J,
488  WorkCompressMPI<scalar_t>& w, int& self, int lvl);
489  virtual void get_extraction_indices
490  (std::vector<std::vector<std::size_t>>& I,
491  std::vector<std::vector<std::size_t>>& J, std::vector<DistMW_t>& B,
492  const BLACSGrid* lg, WorkCompressMPI<scalar_t>& w, int& self, int lvl);
493  virtual void extract_D_B
494  (const delemw_t& Aelem, const BLACSGrid* lg, const opts_t& opts,
495  WorkCompressMPI<scalar_t>& w, int lvl);
496 
497  virtual void apply_fwd
498  (const DistSubLeaf<scalar_t>& B, WorkApplyMPI<scalar_t>& w,
499  bool isroot, long long int flops) const;
500  virtual void apply_bwd
501  (const DistSubLeaf<scalar_t>& B, scalar_t beta,
502  DistSubLeaf<scalar_t>& C, WorkApplyMPI<scalar_t>& w,
503  bool isroot, long long int flops) const;
504  virtual void applyT_fwd
505  (const DistSubLeaf<scalar_t>& B, WorkApplyMPI<scalar_t>& w,
506  bool isroot, long long int flops) const;
507  virtual void applyT_bwd
508  (const DistSubLeaf<scalar_t>& B, scalar_t beta,
509  DistSubLeaf<scalar_t>& C, WorkApplyMPI<scalar_t>& w,
510  bool isroot, long long int flops) const;
511 
512  virtual void factor_recursive
513  (HSSFactorsMPI<scalar_t>& ULV, WorkFactorMPI<scalar_t>& w,
514  const BLACSGrid* lg, bool isroot, bool partial) const;
515 
516  virtual void solve_fwd
517  (const HSSFactorsMPI<scalar_t>& ULV, const DistSubLeaf<scalar_t>& b,
518  WorkSolveMPI<scalar_t>& w, bool partial, bool isroot) const;
519  virtual void solve_bwd
520  (const HSSFactorsMPI<scalar_t>& ULV, DistSubLeaf<scalar_t>& x,
521  WorkSolveMPI<scalar_t>& w, bool isroot) const;
522 
523  virtual void extract_fwd
524  (WorkExtractMPI<scalar_t>& w, const BLACSGrid* lg, bool odiag) const;
525  virtual void extract_bwd
526  (std::vector<Triplet<scalar_t>>& triplets,
527  const BLACSGrid* lg, WorkExtractMPI<scalar_t>& w) const;
528  virtual void extract_fwd
529  (WorkExtractBlocksMPI<scalar_t>& w, const BLACSGrid* lg,
530  std::vector<bool>& odiag) const;
531  virtual void extract_bwd
532  (std::vector<std::vector<Triplet<scalar_t>>>& triplets,
533  const BLACSGrid* lg, WorkExtractBlocksMPI<scalar_t>& w) const;
534 
535  virtual void apply_UV_big
536  (DistSubLeaf<scalar_t>& Theta, DistM_t& Uop,
537  DistSubLeaf<scalar_t>& Phi, DistM_t& Vop,
538  long long int& flops) const;
539 
540  virtual void redistribute_to_tree_to_buffers
541  (const DistM_t& A, std::size_t Arlo, std::size_t Aclo,
542  std::vector<std::vector<scalar_t>>& sbuf, int dest);
543  virtual void redistribute_to_tree_from_buffers
544  (const DistM_t& A, std::size_t Arlo, std::size_t Aclo,
545  std::vector<scalar_t*>& pbuf);
546  virtual void delete_redistributed_input();
547 
548  friend class HSSMatrixMPI<scalar_t>;
549 #endif //defined(STRUMPACK_USE_MPI)
550  };
551 
552  } // end namespace HSS
553 } // end namespace strumpack
554 
555 
556 #endif // HSS_MATRIX_BASE_HPP
strumpack::BLACSGrid
This is a small wrapper class around a BLACS grid and a BLACS context.
Definition: BLACSGrid.hpp:66
strumpack::HSS::HSSMatrixBase::~HSSMatrixBase
virtual ~HSSMatrixBase()=default
strumpack::HSS::HSSMatrixBase::clone
virtual std::unique_ptr< HSSMatrixBase< scalar_t > > clone() const =0
strumpack::HSS::HSSMatrixBase::leaf
bool leaf() const
Definition: HSSMatrixBase.hpp:171
strumpack::HSS::HSSMatrixBase::HSSMatrixBase
HSSMatrixBase(std::size_t m, std::size_t n, bool active)
strumpack::HSS::HSSOptions
Class containing several options for the HSS code and data-structures.
Definition: HSSOptions.hpp:117
strumpack::HSS::HSSMatrixBase::draw
virtual void draw(std::ostream &of, std::size_t rlo, std::size_t clo) const
Definition: HSSMatrixBase.hpp:321
strumpack::HSS::HSSMatrixBase::rank
virtual std::size_t rank() const =0
DenseMatrix.hpp
Contains the DenseMatrix and DenseMatrixWrapper classes, simple wrappers around BLAS/LAPACK style den...
strumpack
Definition: StrumpackOptions.hpp:42
strumpack::DistributedMatrix
Definition: CompressedSparseMatrix.hpp:58
strumpack::HSS::HSSMatrixBase::print_info
virtual void print_info(std::ostream &out=std::cout, std::size_t roff=0, std::size_t coff=0) const =0
strumpack::DenseMatrixWrapper
Like DenseMatrix, this class represents a matrix, stored in column major format, to allow direct use ...
Definition: DenseMatrix.hpp:946
strumpack::HSS::HSSMatrixBase::levels
virtual std::size_t levels() const =0
strumpack::HSS::HSSMatrixBase::shift
virtual void shift(scalar_t sigma)=0
strumpack::HSS::HSSMatrixBase::rows
std::size_t rows() const
Definition: HSSMatrixBase.hpp:159
strumpack::DenseMatrix< scalar_t >
strumpack::DistributedMatrixWrapper
Definition: DistributedMatrix.hpp:271
strumpack::HSS::State::COMPRESSED
@ COMPRESSED
strumpack::HSS::HSSMatrixBase::nonzeros
virtual std::size_t nonzeros() const =0
strumpack::HSS::HSSMatrixBase::is_untouched
bool is_untouched() const
Definition: HSSMatrixBase.hpp:222
strumpack::HSS::HSSFactorsMPI
Contains data related to ULV factorization of a distributed HSS matrix.
Definition: HSSExtraMPI.hpp:185
strumpack::HSS::HSSMatrixBase::set_openmp_task_depth
void set_openmp_task_depth(int depth)
Definition: HSSMatrixBase.hpp:294
strumpack::HSS::HSSMatrixBase::active
bool active() const
Definition: HSSMatrixBase.hpp:233
strumpack::HSS::HSSMatrixBase::cols
std::size_t cols() const
Definition: HSSMatrixBase.hpp:165
strumpack::HSS::State::UNTOUCHED
@ UNTOUCHED
HSSOptions.hpp
Contains the HSSOptions class as well as general routines for HSS options.
strumpack::HSS::State
State
Definition: HSSExtra.hpp:45
strumpack::HSS::HSSMatrixBase::dims
std::pair< std::size_t, std::size_t > dims() const
Definition: HSSMatrixBase.hpp:151
strumpack::HSS::HSSMatrixBase::child
const HSSMatrixBase< scalar_t > & child(int c) const
Definition: HSSMatrixBase.hpp:182
strumpack::CompressionType::HSS
@ HSS
strumpack::HSS::HSSMatrixBase::is_compressed
bool is_compressed() const
Definition: HSSMatrixBase.hpp:207
strumpack::HSS::HSSMatrixBase
Abstract base class for Hierarchically Semi-Separable (HSS) matrices.
Definition: HSSMatrixBase.hpp:79
strumpack::HSS::HSSMatrixBase::operator=
HSSMatrixBase< scalar_t > & operator=(const HSSMatrixBase< scalar_t > &other)
strumpack::HSS::HSSMatrixBase::child
HSSMatrixBase< scalar_t > & child(int c)
Definition: HSSMatrixBase.hpp:195
strumpack::HSS::HSSMatrixBase::memory
virtual std::size_t memory() const =0