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/lac/lapack_full_matrix.h>
#include <deal.II/lac/utilities.h>
 
#include <boost/signals2/signal.hpp>
 
#include <memory>
 
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
 
namespace internal
{
  namespace QRImplementation
  {
    // We want to avoid including our own LAPACK wrapper header in any external
    // headers to avoid possible conflicts with other packages that may define
    // their own such header. At the same time we want to be able to call some
    // LAPACK functions from the template functions below. To resolve both
    // problems define some extra wrappers here that can be in the header:
    template <typename Number>
    void
    call_trmv(const char            uplo,
              const char            trans,
              const char            diag,
              const types::blas_int n,
              const Number *        a,
              const types::blas_int lda,
              Number *              x,
              const types::blas_int incx);
 
    template <typename Number>
    void
    call_trtrs(const char            uplo,
               const char            trans,
               const char            diag,
               const types::blas_int n,
               const types::blas_int nrhs,
               const Number *        a,
               const types::blas_int lda,
               Number *              b,
               const types::blas_int ldb,
               types::blas_int *     info);
  } // namespace QRImplementation
} // namespace internal
 
 
 
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;
  internal::QRImplementation::call_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::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;
      internal::QRImplementation::call_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::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::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;
  internal::QRImplementation::call_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;
  internal::QRImplementation::call_trmv(
    'U', 'T', 'N', N, &this->R(0, 0), lda, &y[0], incx);
}
 
#endif // no DOXYGEN
 
DEAL_II_NAMESPACE_CLOSE
 
#endif