qr.h

Go to the documentation of this file.

// ---------------------------------------------------------------------
//
// Copyright (C) 2018 - 2020 by the deal.II authors
//
// This file is part of the deal.II library.
//
// The deal.II library is free software; you can use it, redistribute
// it, and/or modify it under the terms of the GNU Lesser General
// Public License as published by the Free Software Foundation; either
// version 2.1 of the License, or (at your option) any later version.
// The full text of the license can be found in the file LICENSE.md at
// the top level directory of deal.II.
//
// ---------------------------------------------------------------------

#ifndef dealii_qr_h
#define dealii_qr_h

#include <deal.II/base/config.h>

#include <deal.II/base/exceptions.h>
#include <deal.II/base/std_cxx14/memory.h>

#include <deal.II/lac/lapack_full_matrix.h>
#include <deal.II/lac/lapack_templates.h>
#include <deal.II/lac/utilities.h>

#include <boost/signals2/signal.hpp>

DEAL_II_NAMESPACE_OPEN

template <typename VectorType>
class BaseQR
{
  using Number = typename VectorType::value_type;

protected:
  BaseQR();

public:
  virtual ~BaseQR() = default;

  virtual bool
  append_column(const VectorType &column) = 0;

  virtual void
  remove_column(const unsigned int k = 0) = 0;

  unsigned int
  size() const;

  const LAPACKFullMatrix<Number> &
  get_R() const;

  void
  solve(Vector<Number> &      x,
        const Vector<Number> &y,
        const bool            transpose = false) const;

  virtual void
  multiply_with_Q(VectorType &y, const Vector<Number> &x) const = 0;

  virtual void
  multiply_with_QT(Vector<Number> &y, const VectorType &x) const = 0;

  virtual void
  multiply_with_A(VectorType &y, const Vector<Number> &x) const = 0;

  virtual void
  multiply_with_AT(Vector<Number> &y, const VectorType &x) const = 0;

  boost::signals2::connection
  connect_givens_slot(
    const std::function<void(const unsigned int           i,
                             const unsigned int           j,
                             const std::array<Number, 3> &csr)> &slot);

protected:
  void
  multiply_with_cols(VectorType &y, const Vector<Number> &x) const;

  void
  multiply_with_colsT(Vector<Number> &y, const VectorType &x) const;

  std::vector<std::unique_ptr<VectorType>> columns;

  LAPACKFullMatrix<Number> R;

  unsigned int current_size;

  boost::signals2::signal<void(const unsigned int i,
                               const unsigned int j,
                               const std::array<Number, 3> &)>
    givens_signal;
};

// clang-format off
// clang-format on
template <typename VectorType>
class QR : public BaseQR<VectorType>
{
public:
  using Number = typename VectorType::value_type;

  QR();

  virtual ~QR() = default;

  virtual bool
  append_column(const VectorType &column);

  virtual void
  remove_column(const unsigned int k = 0);

  virtual void
  multiply_with_Q(VectorType &y, const Vector<Number> &x) const;

  virtual void
  multiply_with_QT(Vector<Number> &y, const VectorType &x) const;

  virtual void
  multiply_with_A(VectorType &y, const Vector<Number> &x) const;

  virtual void
  multiply_with_AT(Vector<Number> &y, const VectorType &x) const;

private:
  void
  apply_givens_rotation(const unsigned int i, const unsigned int k);

  VectorType tmp;
};



template <typename VectorType>
class ImplicitQR : public BaseQR<VectorType>
{
public:
  using Number = typename VectorType::value_type;

  ImplicitQR();

  virtual ~ImplicitQR() = default;

  virtual bool
  append_column(const VectorType &column);

  virtual void
  remove_column(const unsigned int k = 0);

  virtual void
  multiply_with_Q(VectorType &y, const Vector<Number> &x) const;

  virtual void
  multiply_with_QT(Vector<Number> &y, const VectorType &x) const;

  virtual void
  multiply_with_A(VectorType &y, const Vector<Number> &x) const;

  virtual void
  multiply_with_AT(Vector<Number> &y, const VectorType &x) const;

  boost::signals2::connection
  connect_append_column_slot(
    const std::function<bool(const Vector<Number> &u,
                             const Number &        rho2,
                             const Number &        col_norm_sqr)> &slot);

private:
  void
  apply_givens_rotation(const unsigned int i, const unsigned int k);

  boost::signals2::signal<bool(const Vector<Number> &u,
                               const Number &        rho,
                               const Number &        col_norm_sqr)>
    column_signal;
};

// -------------------  inline and template functions ----------------
#ifndef DOXYGEN



template <typename VectorType>
BaseQR<VectorType>::BaseQR()
  : current_size(0)
{
  R.set_property(LAPACKSupport::upper_triangular);
}



template <typename VectorType>
unsigned int
BaseQR<VectorType>::size() const
{
  return current_size;
}



template <typename VectorType>
const LAPACKFullMatrix<typename BaseQR<VectorType>::Number> &
BaseQR<VectorType>::get_R() const
{
  return R;
}



template <typename VectorType>
void
BaseQR<VectorType>::solve(Vector<Number> &      x,
                          const Vector<Number> &y,
                          const bool            transpose) const
{
  Assert(x.size() == this->current_size,
         ExcDimensionMismatch(x.size(), this->current_size));
  Assert(y.size() == this->current_size,
         ExcDimensionMismatch(y.size(), this->current_size));

  // copy if the two vectors are not the same
  if (&x != &y)
    x = y;

  const int lda   = this->current_size;
  const int ldb   = this->current_size;
  const int N     = this->current_size;
  const int n_rhs = 1;
  int       info  = 0;
  trtrs("U",
        transpose ? "T" : "N",
        "N",
        &N,
        &n_rhs,
        &this->R(0, 0),
        &lda,
        &x(0),
        &ldb,
        &info);
}



template <typename VectorType>
void
BaseQR<VectorType>::multiply_with_cols(VectorType &          y,
                                       const Vector<Number> &x) const
{
  Assert(x.size() == this->current_size,
         ExcDimensionMismatch(x.size(), this->current_size));

  y = 0.;
  for (unsigned int j = 0; j < this->current_size; ++j)
    y.add(x[j], *this->columns[j]);
}



template <typename VectorType>
void
BaseQR<VectorType>::multiply_with_colsT(Vector<Number> &  y,
                                        const VectorType &x) const
{
  Assert(y.size() == this->current_size,
         ExcDimensionMismatch(y.size(), this->current_size));

  for (unsigned int j = 0; j < this->current_size; ++j)
    y[j] = (*this->columns[j]) * x;
}



template <class VectorType>
boost::signals2::connection
BaseQR<VectorType>::connect_givens_slot(
  const std::function<void(const unsigned int i,
                           const unsigned int j,
                           const std::array<Number, 3> &)> &slot)
{
  return givens_signal.connect(slot);
}



template <class VectorType>
boost::signals2::connection
ImplicitQR<VectorType>::connect_append_column_slot(
  const std::function<bool(const Vector<Number> &u,
                           const Number &        rho,
                           const Number &        col_norm_sqr)> &slot)
{
  return column_signal.connect(slot);
}



template <typename VectorType>
ImplicitQR<VectorType>::ImplicitQR()
  : BaseQR<VectorType>()
{}



template <typename VectorType>
bool
ImplicitQR<VectorType>::append_column(const VectorType &column)
{
  if (this->current_size == 0)
    {
      this->R.grow_or_shrink(this->current_size + 1);
      this->columns.push_back(std_cxx14::make_unique<VectorType>(column));
      this->R(0, 0) = column.l2_norm();
      ++this->current_size;
    }
  else
    {
      // first get scalar products with A^T
      Vector<Number> u(this->current_size);
      this->multiply_with_AT(u, column);

      // now solve R^T x = (A^T * column)
      const int lda   = this->current_size;
      const int ldb   = this->current_size;
      const int N     = this->current_size;
      const int n_rhs = 1;
      int       info  = 0;
      trtrs(
        "U", "T", "N", &N, &n_rhs, &this->R(0, 0), &lda, &u(0), &ldb, &info);

      // finally get the diagonal element:
      // rho2 = |column|^2 - |u|^2
      const Number column_norm_sqr = column.norm_sqr();
      const Number rho2            = column_norm_sqr - u.norm_sqr();
      const bool   linearly_independent =
        column_signal.empty() ? rho2 > 0 :
                                column_signal(u, rho2, column_norm_sqr).get();

      // bail out if it turns out to be linearly dependent
      if (!linearly_independent)
        return false;

      // at this point we update is successful and we can enlarge R
      // and store the column:
      this->columns.push_back(std_cxx14::make_unique<VectorType>(column));
      this->R.grow_or_shrink(this->current_size + 1);
      this->R(this->current_size, this->current_size) = std::sqrt(rho2);
      for (unsigned int i = 0; i < this->current_size; ++i)
        this->R(i, this->current_size) = u(i);

      this->current_size++;
    }

  return true;
}



template <typename VectorType>
void
ImplicitQR<VectorType>::apply_givens_rotation(const unsigned int i,
                                              const unsigned int k)
{
  AssertIndexRange(i, k);
  AssertIndexRange(k, this->current_size);
  const std::array<Number, 3> csr =
    ::Utilities::LinearAlgebra::givens_rotation<Number>(this->R(i, k),
                                                              this->R(k, k));

  // first, set k'th column:
  this->R(i, k) = csr[2];
  this->R(k, k) = 0.;
  // now do the rest:
  for (unsigned int j = 0; j < this->R.n(); ++j)
    if (j != k)
      {
        const Number t = this->R(i, j);
        this->R(i, j)  = csr[0] * this->R(i, j) + csr[1] * this->R(k, j);
        this->R(k, j)  = -csr[1] * t + csr[0] * this->R(k, j);
      }

  if (!this->givens_signal.empty())
    this->givens_signal(i, k, csr);
}



template <typename VectorType>
void
ImplicitQR<VectorType>::remove_column(const unsigned int k)
{
  // before actually removing a column from Q and resizing R,
  // apply givens rotations to bring H into upper triangular form:
  for (unsigned int j = k + 1; j < this->R.n(); ++j)
    {
      const unsigned int i = j - 1;
      apply_givens_rotation(i, j);
    }

  // remove last row and k-th column
  --this->current_size;
  this->R.remove_row_and_column(this->current_size, k);

  // Finally remove the column from A
  this->columns.erase(this->columns.begin() + k);
}



template <typename VectorType>
void
ImplicitQR<VectorType>::multiply_with_Q(VectorType &          y,
                                        const Vector<Number> &x) const
{
  // A = QR
  // A R^{-1} = Q
  Vector<Number> x1 = x;
  BaseQR<VectorType>::solve(x1, x1, false);
  multiply_with_A(y, x1);
}



template <typename VectorType>
void
ImplicitQR<VectorType>::multiply_with_QT(Vector<Number> &  y,
                                         const VectorType &x) const
{
  // A = QR
  // A^T = R^T Q^T
  // {R^T}^{-1} A^T = Q^T
  multiply_with_AT(y, x);
  BaseQR<VectorType>::solve(y, y, true);
}



template <typename VectorType>
void
ImplicitQR<VectorType>::multiply_with_A(VectorType &          y,
                                        const Vector<Number> &x) const
{
  BaseQR<VectorType>::multiply_with_cols(y, x);
}



template <typename VectorType>
void
ImplicitQR<VectorType>::multiply_with_AT(Vector<Number> &  y,
                                         const VectorType &x) const
{
  BaseQR<VectorType>::multiply_with_colsT(y, x);
}



template <typename VectorType>
QR<VectorType>::QR()
  : BaseQR<VectorType>()
{}



template <typename VectorType>
bool
QR<VectorType>::append_column(const VectorType &column)
{
  // resize R:
  this->R.grow_or_shrink(this->current_size + 1);
  this->columns.push_back(std_cxx14::make_unique<VectorType>(column));

  // now a Gram-Schmidt part: orthonormalize the new column
  // against everything we have so far:
  auto &last_col = *this->columns.back();
  for (unsigned int i = 0; i < this->current_size; ++i)
    {
      const auto &i_col              = *this->columns[i];
      this->R(i, this->current_size) = i_col * last_col;
      last_col.add(-this->R(i, this->current_size), i_col);
    }

  this->R(this->current_size, this->current_size) = last_col.l2_norm();

  Assert(this->R(this->current_size, this->current_size) > 0.,
         ExcDivideByZero());
  last_col *= 1. / this->R(this->current_size, this->current_size);

  ++this->current_size;
  return true;
}



template <typename VectorType>
void
QR<VectorType>::apply_givens_rotation(const unsigned int i,
                                      const unsigned int k)
{
  AssertIndexRange(i, k);
  AssertIndexRange(k, this->current_size);
  const std::array<Number, 3> csr =
    ::Utilities::LinearAlgebra::givens_rotation<Number>(this->R(i, k),
                                                              this->R(k, k));

  // first, set k'th column:
  this->R(i, k) = csr[2];
  this->R(k, k) = 0.;
  // now do the rest:
  for (unsigned int j = 0; j < this->R.n(); ++j)
    if (j != k)
      {
        const Number t = this->R(i, j);
        this->R(i, j)  = csr[0] * this->R(i, j) + csr[1] * this->R(k, j);
        this->R(k, j)  = -csr[1] * t + csr[0] * this->R(k, j);
      }

  // now adjust i,k columns due to multiplication with the
  // transpose Givens matrix from right:
  auto &col_i = *this->columns[i];
  auto &col_k = *this->columns[k];
  // save column i:
  tmp = col_i;
  col_i.sadd(csr[0], csr[1], col_k);
  col_k.sadd(csr[0], -csr[1], tmp);

  if (!this->givens_signal.empty())
    this->givens_signal(i, k, csr);
}



template <typename VectorType>
void
QR<VectorType>::remove_column(const unsigned int k)
{
  AssertIndexRange(k, this->current_size);
  Assert(this->current_size > 0,
         ExcMessage("Can not remove a column if QR is empty"));
  // apply a sequence of Givens rotations
  // see section 6.5 "Updating matrix factorizations" in Golub 2013, Matrix
  // computations

  // So we want to have QR for \tilde A \in R^{m*(n-1)}
  // if we remove the column k, we end up with upper Hessenberg matrix
  //      x x x x x
  //        x x x x
  // H =      x x x
  //          x x x
  //            x x
  //              x
  // where k = 2 (3rd column), m = 7, n = 6
  //
  // before actually removing a column from Q and resizing R,
  // apply givens rotations to bring H into upper triangular form:
  for (unsigned int j = k + 1; j < this->R.n(); ++j)
    {
      const unsigned int i = j - 1;
      apply_givens_rotation(i, j);
    }

  // now we can throw away the column from Q and adjust R
  // since we do thin-QR, after Givens rotations we need to throw
  // away the last column:
  const unsigned int size_minus_1 = this->columns.size() - 1;
  this->columns.erase(this->columns.begin() + size_minus_1);

  // remove last row and k-th column
  --this->current_size;
  this->R.remove_row_and_column(this->current_size, k);
}



template <typename VectorType>
void
QR<VectorType>::multiply_with_Q(VectorType &y, const Vector<Number> &x) const
{
  BaseQR<VectorType>::multiply_with_cols(y, x);
}



template <typename VectorType>
void
QR<VectorType>::multiply_with_QT(Vector<Number> &y, const VectorType &x) const
{
  BaseQR<VectorType>::multiply_with_colsT(y, x);
}



template <typename VectorType>
void
QR<VectorType>::multiply_with_A(VectorType &y, const Vector<Number> &x) const
{
  Vector<Number> x1   = x;
  const int      N    = this->current_size;
  const int      lda  = N;
  const int      incx = 1;
  trmv("U", "N", "N", &N, &this->R(0, 0), &lda, &x1[0], &incx);

  multiply_with_Q(y, x1);
}



template <typename VectorType>
void
QR<VectorType>::multiply_with_AT(Vector<Number> &y, const VectorType &x) const
{
  multiply_with_QT(y, x);

  const int N    = this->current_size;
  const int lda  = N;
  const int incx = 1;
  trmv("U", "T", "N", &N, &this->R(0, 0), &lda, &y[0], &incx);
}

#endif // no DOXYGEN

DEAL_II_NAMESPACE_CLOSE

#endif