sparse-matrix.h

Go to the documentation of this file.

// matrix/sparse-matrix.h

// Copyright  2015  Johns Hopkins University (author: Daniel Povey)
//            2015  Guoguo Chen
//            2017  Shiyin Kang


// See ../../COPYING for clarification regarding multiple authors
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//  http://www.apache.org/licenses/LICENSE-2.0
//
// THIS CODE IS PROVIDED *AS IS* BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
// KIND, EITHER EXPRESS OR IMPLIED, INCLUDING WITHOUT LIMITATION ANY IMPLIED
// WARRANTIES OR CONDITIONS OF TITLE, FITNESS FOR A PARTICULAR PURPOSE,
// MERCHANTABLITY OR NON-INFRINGEMENT.
// See the Apache 2 License for the specific language governing permissions and
// limitations under the License.

#ifndef KALDI_MATRIX_SPARSE_MATRIX_H_
#define KALDI_MATRIX_SPARSE_MATRIX_H_ 1

#include <utility>
#include <vector>

#include "matrix/matrix-common.h"
#include "matrix/kaldi-matrix.h"
#include "matrix/kaldi-vector.h"
#include "matrix/compressed-matrix.h"

namespace kaldi {



template <typename Real>
class SparseVector {
 public:
  MatrixIndexT Dim() const { return dim_; }

  Real Sum() const;

  template <class OtherReal>
  void CopyElementsToVec(VectorBase<OtherReal> *vec) const;

  // *vec += alpha * *this.
  template <class OtherReal>
  void AddToVec(Real alpha,
                VectorBase<OtherReal> *vec) const;

  template <class OtherReal>
  void CopyFromSvec(const SparseVector<OtherReal> &other);

  SparseVector<Real> &operator = (const SparseVector<Real> &other);

  SparseVector(const SparseVector<Real> &other) { *this = other; }

  void Swap(SparseVector<Real> *other);

  // Returns the maximum value in this row and outputs the index associated with
  // it.  This is not the index into the Data() pointer, it is the index into
  // the vector it represents, i.e. the .first value in the pair.
  // If this vector's Dim() is zero it is an error to call this function.
  // If all the elements stored were negative and there underlying vector had
  // zero indexes not listed in the elements, or if no elements are stored, it
  // will return the first un-listed index, whose value (implicitly) is zero.
  Real Max(int32 *index) const;

  MatrixIndexT NumElements() const { return pairs_.size(); }

  const std::pair<MatrixIndexT, Real> &GetElement(MatrixIndexT i) const {
    return pairs_[i];
  }

  // returns pointer to element data, or NULL if empty (use with NumElements()).
  std::pair<MatrixIndexT, Real> *Data();

  // returns pointer to element data, or NULL if empty (use with NumElements());
  // const version
  const std::pair<MatrixIndexT, Real> *Data() const;

  void SetRandn(BaseFloat zero_prob);

  SparseVector(): dim_(0) { }

  explicit SparseVector(MatrixIndexT dim): dim_(dim) { KALDI_ASSERT(dim >= 0); }

  // constructor from pairs; does not assume input pairs are sorted and uniq
  SparseVector(MatrixIndexT dim,
               const std::vector<std::pair<MatrixIndexT, Real> > &pairs);

  // constructor from a VectorBase that keeps only the nonzero elements of 'vec'.
  explicit SparseVector(const VectorBase<Real> &vec);

  void Resize(MatrixIndexT dim, MatrixResizeType resize_type = kSetZero);

  void Write(std::ostream &os, bool binary) const;

  void Read(std::istream &os, bool binary);

  void Scale(Real alpha);

 private:
  MatrixIndexT dim_;
  // pairs of (row-index, value).  Stored in sorted order with no duplicates.
  // For now we use std::vector, but we could change this.
  std::vector<std::pair<MatrixIndexT, Real> > pairs_;
};


template <typename Real>
Real VecSvec(const VectorBase<Real> &vec,
             const SparseVector<Real> &svec);



template <typename Real>
class SparseMatrix {
 public:
  MatrixIndexT NumRows() const;

  MatrixIndexT NumCols() const;

  MatrixIndexT NumElements() const;

  Real Sum() const;

  Real FrobeniusNorm() const;


  explicit SparseMatrix(const MatrixBase<Real> &mat);

  template <class OtherReal>
  void CopyToMat(MatrixBase<OtherReal> *other,
                 MatrixTransposeType t = kNoTrans) const;

  void CopyElementsToVec(VectorBase<Real> *other) const;

  template<class OtherReal>
  void CopyFromSmat(const SparseMatrix<OtherReal> &other,
                    MatrixTransposeType trans = kNoTrans);

  void AddToMat(BaseFloat alpha, MatrixBase<Real> *other,
                MatrixTransposeType t = kNoTrans) const;

  SparseMatrix<Real> &operator = (const SparseMatrix<Real> &other);

  SparseMatrix(const SparseMatrix<Real> &other, MatrixTransposeType trans =
                   kNoTrans) {
    this->CopyFromSmat(other, trans);
  }

  void Swap(SparseMatrix<Real> *other);

  // returns pointer to element data, or NULL if empty (use with NumElements()).
  SparseVector<Real> *Data();

  // returns pointer to element data, or NULL if empty (use with NumElements());
  // const version
  const SparseVector<Real> *Data() const;

  // initializer from the type that elsewhere in Kaldi is referred to as type
  // Posterior. indexed first by row-index; the pairs are (column-index, value),
  // and the constructor does not require them to be sorted and uniq.
  SparseMatrix(
      int32 dim,
      const std::vector<std::vector<std::pair<MatrixIndexT, Real> > > &pairs);

  void SetRandn(BaseFloat zero_prob);

  void Write(std::ostream &os, bool binary) const;

  void Read(std::istream &os, bool binary);

  const SparseVector<Real> &Row(MatrixIndexT r) const;

  void SetRow(int32 r, const SparseVector<Real> &vec);

  void SelectRows(const std::vector<int32> &row_indexes,
                  const SparseMatrix<Real> &smat_other);


  void AppendSparseMatrixRows(std::vector<SparseMatrix<Real> > *inputs);

  SparseMatrix() { }

  SparseMatrix(int32 num_rows, int32 num_cols) { Resize(num_rows, num_cols); }

  SparseMatrix(const std::vector<int32> &indexes, int32 dim,
               MatrixTransposeType trans = kNoTrans);

  SparseMatrix(const std::vector<int32> &indexes,
               const VectorBase<Real> &weights, int32 dim,
               MatrixTransposeType trans = kNoTrans);

  void Resize(MatrixIndexT rows, MatrixIndexT cols,
              MatrixResizeType resize_type = kSetZero);

  void Scale(Real alpha);

  // Use the Matrix::CopyFromSmat() function to copy from this to Matrix.  Also
  // see Matrix::AddSmat().  There is not very extensive functionality for
  // SparseMat just yet (e.g. no matrix multiply); we will add things as needed
  // and as it seems necessary.
 private:
  // vector of SparseVectors, all of same dime (use an stl vector for now; this
  // could change).
  std::vector<SparseVector<Real> > rows_;
};


template<typename Real>
Real TraceMatSmat(const MatrixBase<Real> &A,
                  const SparseMatrix<Real> &B,
                  MatrixTransposeType trans = kNoTrans);


enum GeneralMatrixType {
  kFullMatrix,
  kCompressedMatrix,
  kSparseMatrix
};

class GeneralMatrix {
 public:
  GeneralMatrixType Type() const;

  void Compress();  // If it was a full matrix, compresses, changing Type() to
                    // kCompressedMatrix; otherwise does nothing.

  void Uncompress();  // If it was a compressed matrix, uncompresses, changing
                      // Type() to kFullMatrix; otherwise does nothing.

  void Write(std::ostream &os, bool binary) const;


  void Read(std::istream &is, bool binary);

  const SparseMatrix<BaseFloat> &GetSparseMatrix() const;

  void SwapSparseMatrix(SparseMatrix<BaseFloat> *smat);

  const CompressedMatrix &GetCompressedMatrix() const;

  void SwapCompressedMatrix(CompressedMatrix *cmat);

  const Matrix<BaseFloat>& GetFullMatrix() const;

  void GetMatrix(Matrix<BaseFloat> *mat) const;

  void SwapFullMatrix(Matrix<BaseFloat> *mat);

  void CopyToMat(MatrixBase<BaseFloat> *mat,
                 MatrixTransposeType trans = kNoTrans) const;

  void CopyToMat(CuMatrixBase<BaseFloat> *cu_mat,
                 MatrixTransposeType trans = kNoTrans) const;

  void AddToMat(BaseFloat alpha, MatrixBase<BaseFloat> *mat,
                MatrixTransposeType trans = kNoTrans) const;

  void AddToMat(BaseFloat alpha, CuMatrixBase<BaseFloat> *cu_mat,
                MatrixTransposeType trans = kNoTrans) const;

  void Scale(BaseFloat alpha);

  GeneralMatrix &operator= (const MatrixBase<BaseFloat> &mat);

  GeneralMatrix &operator= (const CompressedMatrix &mat);

  GeneralMatrix &operator= (const SparseMatrix<BaseFloat> &smat);

  MatrixIndexT NumRows() const;

  MatrixIndexT NumCols() const;

  explicit GeneralMatrix(const MatrixBase<BaseFloat> &mat) { *this = mat; }

  explicit GeneralMatrix(const CompressedMatrix &cmat) { *this = cmat; }

  explicit GeneralMatrix(const SparseMatrix<BaseFloat> &smat) { *this = smat; }

  GeneralMatrix() { }
  // Assignment operator.
  GeneralMatrix &operator =(const GeneralMatrix &other);
  // Copy constructor
  GeneralMatrix(const GeneralMatrix &other) { *this = other; }
  // Sets to the empty matrix.
  void Clear();
  // shallow swap
  void Swap(GeneralMatrix *other);
 private:
  // We don't explicitly store the type of the matrix.  Rather, we make
  // sure that only one of the matrices is ever nonempty, and the Type()
  // returns that one, or kFullMatrix if all are empty.
  Matrix<BaseFloat> mat_;
  CompressedMatrix cmat_;
  SparseMatrix<BaseFloat> smat_;
};


void AppendGeneralMatrixRows(const std::vector<const GeneralMatrix *> &src,
                             GeneralMatrix *mat);


template <typename Real>
void FilterSparseMatrixRows(const SparseMatrix<Real> &in,
                            const std::vector<bool> &keep_rows,
                            SparseMatrix<Real> *out);

template <typename Real>
void FilterMatrixRows(const Matrix<Real> &in,
                      const std::vector<bool> &keep_rows,
                      Matrix<Real> *out);

void FilterCompressedMatrixRows(const CompressedMatrix &in,
                                const std::vector<bool> &keep_rows,
                                Matrix<BaseFloat> *out);


void FilterGeneralMatrixRows(const GeneralMatrix &in,
                             const std::vector<bool> &keep_rows,
                             GeneralMatrix *out);

void ExtractRowRangeWithPadding(
    const GeneralMatrix &in,
    int32 row_offset,
    int32 num_rows,
    GeneralMatrix *out);




}  // namespace kaldi

#endif  // KALDI_MATRIX_SPARSE_MATRIX_H_