Re: [eigen] Sparse Module Patch |
[ Thread Index |
Date Index
| More lists.tuxfamily.org/eigen Archives
]
- To: eigen@xxxxxxxxxxxxxxxxxxx
- Subject: Re: [eigen] Sparse Module Patch
- From: Daniel Gómez <dgomezferro@xxxxxxxxx>
- Date: Tue, 2 Sep 2008 12:56:50 +0200
- Dkim-signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:received:received:to:subject:date:user-agent :references:in-reply-to:mime-version:content-type:message-id:from; bh=YAB8eWX5GAalSSJ+3IYrGNq3NcPvHgxERELOcAcOxVI=; b=GizPHzV2K15J+lLzFVgpS/Iizq6I1bKcb8q3pCr4N9ZW2+stRFXgbELnb7Z9ukLjKb Sk7V42NpMlAzYB0yND3TNisYlHbTSEYmCe46lPyn833lcmbYNbnBwjlxvnuK71Ddj1jx sWdFf0g5QuxMRF2KArttsalR9+2rx5dGIseZw=
- Domainkey-signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=to:subject:date:user-agent:references:in-reply-to:mime-version :content-type:message-id:from; b=KIBXC6m0nvxhT9CPz5tme9LL+eabS7k7KkYYLqo7wxPNTUDj7pk2ELJztNB2lOQEc8 106jlXIfy8pXi0NiEPM2WmqpdvveqfrIFuTu1NEYFI0JbrdfWja4luZd6xdjeFEP9Y9U x5zbqA2DjuOiT34p9GZyjGekeer+FO0EkIAv0=
Hello,
On Monday 01 September 2008 13:22:59 Gael Guennebaud wrote:
> Hi Daniel,
>
> sorry I was not very helpful to guide you with that stuff... actually
> now I remember what was the big deal with m.row(i) += xpr; etc....
>
> In fact, m.row(i) += xpr; should not be allowed in the general case
> since this might create new non zero entries...
But m.row(i) = m.row(i)*4; should be allowed? I think it should, it is easy to
implement and efficient, although it may confuse users when m.row(i) =
m.row(j); doesnt work because elements have different indexes.
> so here we need to
> first create a setter/wrapper which allows such expressions. If we
> assume m is row-major, then we have a case of "outer coherent update"
> since the inner vector m.row(i) is updated randomly. Moreover it is
> very likely that the current vector m.row(i) is updated several time
> before we process the next row m.row(i+1). A typical example is in
> SparseProduct.h where the lines 161-248 could be implemented as:
>
> {
> - get an outer coherent wrapper w of the matrix m
> for (int j=0; j<cols; ++j)
> {
> w.processInner(j);
> for (typename Rhs::InnerIterator rhsIt(rhs, j); rhsIt; ++rhsIt)
> w.currentInner() += rhsIt.value() * lhs.col(rhsIt.index());
> }
> } // delete the wrapper
>
> w.processInner(j) would estimate the ratio of non zero entries and
> according to this ratio it will automatically use a temporary dense
> vector (lines 169-186) or a temporary custom linked list...(lines
> 190-248) Perhaps, w.processInner() could take an optional argument to
> specify this ratio manually. (there are some details on the wiki) Then
> w.currentInner() would returns a proxy object with an efficient
> InnerIterator implementation. If it happens the default implementation
> of operator + and operator = using InnerIterators is too slow, then
> you might overwrite the operator =, (and perhaps += and -= as well) ,
> I don't know !
>
> For the API of this "Outer-Coherent-Setter", do as you want... maybe
> a inner(int i) is sufficient (internally it can detect a change of
> current row or column and does the initialization/updates if needed)
>
> That let me thought that SparseSetter could take an additional
> template (or non template ?) parameter to specify if we want to "set
> only" the matrix or update it as well.
>
OK, I will go for that API, if I can think any change that may improve it I'll
let you know. Right now, all other ways of doing it I can think of are at the
expense of efficiency.
>
> BTW, if you only have small trivial changes in the Core module feel
> free to commit your current modif so that we can give you some
> feedback, the Sparse module is currently pretty messy anyway, so don't
> worry !
I attach the current diff. In Core I just changed util/ForwardDeclarations.h
and util/Constants.h . Be free to change tha naming I used if you think its
not right. I also changed Block.h to add the declaration of the
InnerIterator.
> feel free to ask if some parts are not very clear or if you think
> there is a better way to achieve the same goal !
Sure, thank you.
I'll be a bit busy until mid-september as I am preparing an exam, by then I'll
be able to spend a little more time on eigen. By the way, I just received my
SVN account, so no need to complain to anybody hehe.
Daniel
Index: test/sparse.cpp
===================================================================
--- test/sparse.cpp (revision 853939)
+++ test/sparse.cpp (working copy)
@@ -25,9 +25,8 @@
#include "main.h"
#include <Eigen/Sparse>
-template<typename Scalar> void sparse()
+template<typename Scalar> void sparse(int rows, int cols)
{
- int rows = 8, cols = 8;
double density = std::max(8./(rows*cols), 0.01);
typedef Matrix<Scalar,Dynamic,Dynamic> DenseMatrix;
Scalar eps = 1e-6;
@@ -73,6 +72,49 @@
VERIFY_IS_APPROX(m, refMat);
+ // test InnerIterators and Block expressions
+ for(int j=0; j<cols; j++)
+ {
+ for(int i=0; i<rows; i++)
+ {
+ for(int w=1; w<cols-j; w++)
+ {
+ for(int h=1; h<rows-i; h++)
+ {
+ VERIFY_IS_APPROX(m.block(i,j,h,w), refMat.block(i,j,h,w));
+ for(int c=0; c<w; c++)
+ {
+ VERIFY_IS_APPROX(m.block(i,j,h,w).col(c), refMat.block(i,j,h,w).col(c));
+ for(int r=0; r<h; r++)
+ {
+ VERIFY_IS_APPROX(m.block(i,j,h,w).col(c).coeff(r), refMat.block(i,j,h,w).col(c).coeff(r));
+ }
+ }
+ for(int r=0; r<h; r++)
+ {
+ VERIFY_IS_APPROX(m.block(i,j,h,w).row(r), refMat.block(i,j,h,w).row(r));
+ for(int c=0; c<w; c++)
+ {
+ VERIFY_IS_APPROX(m.block(i,j,h,w).row(r).coeff(c), refMat.block(i,j,h,w).row(r).coeff(c));
+ }
+ }
+ }
+ }
+ }
+ }
+
+ for(int c=0; c<cols; c++)
+ {
+ VERIFY_IS_APPROX(m.col(c) + m.col(c), (m + m).col(c));
+ VERIFY_IS_APPROX(m.col(c) + m.col(c), refMat.col(c) + refMat.col(c));
+ }
+
+ for(int r=0; r<rows; r++)
+ {
+ VERIFY_IS_APPROX(m.row(r) + m.row(r), (m + m).row(r));
+ VERIFY_IS_APPROX(m.row(r) + m.row(r), refMat.row(r) + refMat.row(r));
+ }
+
// test SparseSetters
// coherent setter
// TODO extend the MatrixSetter
@@ -102,9 +144,11 @@
}
}
VERIFY_IS_APPROX(m, refMat);
+
}
void test_sparse()
{
- sparse<double>();
+ sparse<double>(8, 8);
+ sparse<double>(16, 16);
}
Index: Eigen/src/Core/Block.h
===================================================================
--- Eigen/src/Core/Block.h (revision 853939)
+++ Eigen/src/Core/Block.h (working copy)
@@ -65,6 +65,8 @@
struct ei_traits<Block<MatrixType, BlockRows, BlockCols, _PacketAccess, _DirectAccessStatus> >
{
typedef typename MatrixType::Scalar Scalar;
+ typedef typename MatrixType::Nested MatrixTypeNested;
+ typedef typename ei_unref<MatrixTypeNested>::type _MatrixTypeNested;
enum{
RowsAtCompileTime = MatrixType::RowsAtCompileTime == 1 ? 1 : BlockRows,
ColsAtCompileTime = MatrixType::ColsAtCompileTime == 1 ? 1 : BlockCols,
@@ -98,6 +100,8 @@
EIGEN_GENERIC_PUBLIC_INTERFACE(Block)
+ class InnerIterator;
+
/** Column or Row constructor
*/
inline Block(const MatrixType& matrix, int i)
@@ -225,6 +229,7 @@
_EIGEN_GENERIC_PUBLIC_INTERFACE(Block, MapBase<Block>)
+ class InnerIterator;
typedef typename ei_traits<Block>::AlignedDerivedType AlignedDerivedType;
EIGEN_INHERIT_ASSIGNMENT_OPERATORS(Block)
Index: Eigen/src/Core/MatrixBase.h
===================================================================
--- Eigen/src/Core/MatrixBase.h (revision 853939)
+++ Eigen/src/Core/MatrixBase.h (working copy)
@@ -155,7 +155,7 @@
/** \returns the number of rows. \sa cols(), RowsAtCompileTime */
inline int rows() const { return derived().rows(); }
- /** \returns the number of columns. \sa row(), ColsAtCompileTime*/
+ /** \returns the number of columns. \sa rows(), ColsAtCompileTime*/
inline int cols() const { return derived().cols(); }
/** \returns the number of coefficients, which is \a rows()*cols().
* \sa rows(), cols(), SizeAtCompileTime. */
Index: Eigen/src/Core/util/Constants.h
===================================================================
--- Eigen/src/Core/util/Constants.h (revision 853939)
+++ Eigen/src/Core/util/Constants.h (working copy)
@@ -211,7 +211,8 @@
enum {
NoDirectAccess = 0,
- HasDirectAccess = DirectAccessBit
+ HasDirectAccess = DirectAccessBit,
+ IsSparse = SparseBit
};
const int FullyCoherentAccessPattern = 0x1;
Index: Eigen/src/Core/util/ForwardDeclarations.h
===================================================================
--- Eigen/src/Core/util/ForwardDeclarations.h (revision 853939)
+++ Eigen/src/Core/util/ForwardDeclarations.h (working copy)
@@ -36,7 +36,8 @@
template<typename ExpressionType> class SwapWrapper;
template<typename MatrixType> class Minor;
template<typename MatrixType, int BlockRows=Dynamic, int BlockCols=Dynamic, int PacketAccess=AsRequested,
- int _DirectAccessStatus = ei_traits<MatrixType>::Flags&DirectAccessBit> class Block;
+ int _DirectAccessStatus = ei_traits<MatrixType>::Flags&DirectAccessBit ? DirectAccessBit
+ : ei_traits<MatrixType>::Flags&SparseBit> class Block;
template<typename MatrixType> class Transpose;
template<typename MatrixType> class Conjugate;
template<typename NullaryOp, typename MatrixType> class CwiseNullaryOp;
Index: Eigen/src/Sparse/SparseMatrixBase.h
===================================================================
--- Eigen/src/Sparse/SparseMatrixBase.h (revision 853939)
+++ Eigen/src/Sparse/SparseMatrixBase.h (working copy)
@@ -139,8 +139,23 @@
}
else
{
- LinkedVectorMatrix<Scalar, RowMajorBit> trans = m.derived();
- s << trans;
+ if (m.cols() == 1) {
+ int row = 0;
+ for (typename Derived::InnerIterator it(m.derived(), 0); it; ++it)
+ {
+ for ( ; row<it.index(); ++row)
+ s << "0" << std::endl;
+ s << it.value() << std::endl;
+ ++row;
+ }
+ for ( ; row<m.rows(); ++row)
+ s << "0" << std::endl;
+ }
+ else
+ {
+ LinkedVectorMatrix<Scalar, RowMajorBit> trans = m.derived();
+ s << trans;
+ }
}
return s;
}
Index: Eigen/src/Sparse/SparseMatrix.h
===================================================================
--- Eigen/src/Sparse/SparseMatrix.h (revision 853939)
+++ Eigen/src/Sparse/SparseMatrix.h (working copy)
@@ -98,7 +98,7 @@
// ^^ optimization: let's first check if it is the last coefficient
// (very common in high level algorithms)
- const int* r = std::lower_bound(&m_data.index(start),&m_data.index(end),inner);
+ const int* r = std::lower_bound(&m_data.index(start),&m_data.index(end-1),inner);
const int id = r-&m_data.index(0);
return ((*r==inner) && (id<end)) ? m_data.value(id) : Scalar(0);
}
@@ -267,7 +267,7 @@
InnerIterator& operator++() { m_id++; return *this; }
- Scalar value() { return m_matrix.m_data.value(m_id); }
+ Scalar value() const { return m_matrix.m_data.value(m_id); }
int index() const { return m_matrix.m_data.index(m_id); }
Index: Eigen/src/Sparse/CoreIterators.h
===================================================================
--- Eigen/src/Sparse/CoreIterators.h (revision 853939)
+++ Eigen/src/Sparse/CoreIterators.h (working copy)
@@ -37,7 +37,7 @@
: m_matrix(mat), m_inner(0), m_outer(outer), m_end(mat.rows())
{}
- Scalar value()
+ Scalar value() const
{
return (Derived::Flags&RowMajorBit) ? m_matrix.coeff(m_outer, m_inner)
: m_matrix.coeff(m_inner, m_outer);
@@ -66,6 +66,80 @@
{}
};
+template<typename MatrixType, int BlockRows, int BlockCols, int PacketAccess, int _DirectAccessStatus>
+class Block<MatrixType, BlockRows, BlockCols, PacketAccess, _DirectAccessStatus>::InnerIterator
+{
+ typedef typename Block::Scalar Scalar;
+ typedef typename ei_traits<Block>::_MatrixTypeNested _MatrixTypeNested;
+ typedef typename _MatrixTypeNested::InnerIterator MatrixTypeIterator;
+ public:
+
+ InnerIterator(const Block& block, int outer)
+ : m_iter(block.m_matrix,(Block::Flags&RowMajor) ? block.m_startRow.value() + outer : block.m_startCol.value() + outer),
+ m_start( (Block::Flags&RowMajor) ? block.m_startCol.value() : block.m_startRow.value()),
+ m_end(m_start + ((Block::Flags&RowMajor) ? block.m_blockCols.value() : block.m_blockRows.value())),
+ m_offset( (Block::Flags&RowMajor) ? block.m_startCol.value() : block.m_startRow.value())
+ {
+ while (m_iter.index()>=0 && m_iter.index()<m_start)
+ ++m_iter;
+ }
+
+ InnerIterator& operator++()
+ {
+ ++m_iter;
+ return *this;
+ }
+
+ Scalar value() const { return m_iter.value(); }
+
+ int index() const { return m_iter.index() - m_offset; }
+
+ operator bool() const { return m_iter && m_iter.index()<m_end; }
+
+ protected:
+ MatrixTypeIterator m_iter;
+ int m_start;
+ int m_end;
+ int m_offset;
+};
+
+template<typename MatrixType, int BlockRows, int BlockCols, int PacketAccess>
+class Block<MatrixType, BlockRows, BlockCols, PacketAccess, IsSparse>::InnerIterator
+{
+ typedef typename Block::Scalar Scalar;
+ typedef typename ei_traits<Block>::_MatrixTypeNested _MatrixTypeNested;
+ typedef typename _MatrixTypeNested::InnerIterator MatrixTypeIterator;
+ public:
+
+ InnerIterator(const Block& block, int outer)
+ : m_iter(block.m_matrix,(Block::Flags&RowMajor) ? block.m_startRow.value() + outer : block.m_startCol.value() + outer),
+ m_start( (Block::Flags&RowMajor) ? block.m_startCol.value() : block.m_startRow.value()),
+ m_end(m_start + ((Block::Flags&RowMajor) ? block.m_blockCols.value() : block.m_blockRows.value())),
+ m_offset( (Block::Flags&RowMajor) ? block.m_startCol.value() : block.m_startRow.value())
+ {
+ while (m_iter.index()>=0 && m_iter.index()<m_start)
+ ++m_iter;
+ }
+
+ InnerIterator& operator++()
+ {
+ ++m_iter;
+ return *this;
+ }
+
+ Scalar value() const { return m_iter.value(); }
+
+ int index() const { return m_iter.index() - m_offset; }
+
+ operator bool() const { return m_iter && m_iter.index()<m_end; }
+
+ protected:
+ MatrixTypeIterator m_iter;
+ int m_start;
+ int m_end;
+ int m_offset;
+};
+
template<typename UnaryOp, typename MatrixType>
class CwiseUnaryOp<UnaryOp,MatrixType>::InnerIterator
{
@@ -133,13 +207,13 @@
++m_lhsIter;
++m_rhsIter;
}
- else if (m_lhsIter && ((!m_rhsIter) || m_lhsIter.index() < m_rhsIter.index()))
+ else if (m_lhsIter && (!m_rhsIter || (m_lhsIter.index() < m_rhsIter.index())))
{
m_id = m_lhsIter.index();
m_value = m_functor(m_lhsIter.value(), Scalar(0));
++m_lhsIter;
}
- else if (m_rhsIter && ((!m_lhsIter) || m_lhsIter.index() > m_rhsIter.index()))
+ else if (m_rhsIter && (!m_lhsIter || (m_lhsIter.index() > m_rhsIter.index())))
{
m_id = m_rhsIter.index();
m_value = m_functor(Scalar(0), m_rhsIter.value());
Index: Eigen/src/Sparse/SparseBlock.h
===================================================================
--- Eigen/src/Sparse/SparseBlock.h (revision 0)
+++ Eigen/src/Sparse/SparseBlock.h (revision 0)
@@ -0,0 +1,122 @@
+// This file is part of Eigen, a lightweight C++ template library
+// for linear algebra. Eigen itself is part of the KDE project.
+//
+// Copyright (C) 2008 Gael Guennebaud <g.gael@xxxxxxx>
+// Copyright (C) 2008 Daniel Gomez Ferro <dgomezferro@xxxxxxxxx>
+//
+// Eigen is free software; you can 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 3 of the License, or (at your option) any later version.
+//
+// Alternatively, you can redistribute it and/or
+// modify it under the terms of the GNU General Public License as
+// published by the Free Software Foundation; either version 2 of
+// the License, or (at your option) any later version.
+//
+// Eigen is distributed in the hope that it will be useful, but WITHOUT ANY
+// WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
+// FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License or the
+// GNU General Public License for more details.
+//
+// You should have received a copy of the GNU Lesser General Public
+// License and a copy of the GNU General Public License along with
+// Eigen. If not, see <http://www.gnu.org/licenses/>.
+
+#ifndef EIGEN_SPARSEBLOCK_H
+#define EIGEN_SPARSEBLOCK_H
+
+template<typename MatrixType, int BlockRows, int BlockCols, int PacketAccess>
+class Block<MatrixType,BlockRows,BlockCols,PacketAccess,IsSparse>
+ : public SparseMatrixBase<Block<MatrixType,BlockRows,BlockCols,PacketAccess,IsSparse> >
+{
+public:
+
+ _EIGEN_GENERIC_PUBLIC_INTERFACE(Block, SparseMatrixBase<Block>)
+ class InnerIterator;
+
+ /** Column or Row constructor
+ */
+ inline Block(const MatrixType& matrix, int i)
+ : m_matrix(matrix),
+ // It is a row if and only if BlockRows==1 and BlockCols==MatrixType::ColsAtCompileTime,
+ // and it is a column if and only if BlockRows==MatrixType::RowsAtCompileTime and BlockCols==1,
+ // all other cases are invalid.
+ // The case a 1x1 matrix seems ambiguous, but the result is the same anyway.
+ m_startRow( (BlockRows==1) && (BlockCols==MatrixType::ColsAtCompileTime) ? i : 0),
+ m_startCol( (BlockRows==MatrixType::RowsAtCompileTime) && (BlockCols==1) ? i : 0),
+ m_blockRows(matrix.rows()), // if it is a row, then m_blockRows has a fixed-size of 1, so no pb to try to overwrite it
+ m_blockCols(matrix.cols()) // same for m_blockCols
+ {
+ ei_assert( (i>=0) && (
+ ((BlockRows==1) && (BlockCols==MatrixType::ColsAtCompileTime) && i<matrix.rows())
+ ||((BlockRows==MatrixType::RowsAtCompileTime) && (BlockCols==1) && i<matrix.cols())));
+ }
+
+ /** Fixed-size constructor
+ */
+ inline Block(const MatrixType& matrix, int startRow, int startCol)
+ : m_matrix(matrix), m_startRow(startRow), m_startCol(startCol),
+ m_blockRows(matrix.rows()), m_blockCols(matrix.cols())
+ {
+ EIGEN_STATIC_ASSERT(RowsAtCompileTime!=Dynamic && RowsAtCompileTime!=Dynamic,this_method_is_only_for_fixed_size);
+ ei_assert(startRow >= 0 && BlockRows >= 1 && startRow + BlockRows <= matrix.rows()
+ && startCol >= 0 && BlockCols >= 1 && startCol + BlockCols <= matrix.cols());
+ }
+
+ /** Dynamic-size constructor
+ */
+ inline Block(const MatrixType& matrix,
+ int startRow, int startCol,
+ int blockRows, int blockCols)
+ : m_matrix(matrix), m_startRow(startRow), m_startCol(startCol),
+ m_blockRows(blockRows), m_blockCols(blockCols)
+ {
+ ei_assert((RowsAtCompileTime==Dynamic || RowsAtCompileTime==blockRows)
+ && (ColsAtCompileTime==Dynamic || ColsAtCompileTime==blockCols));
+ ei_assert(startRow >= 0 && blockRows >= 1 && startRow + blockRows <= matrix.rows()
+ && startCol >= 0 && blockCols >= 1 && startCol + blockCols <= matrix.cols());
+ }
+
+ inline int rows() const { return m_blockRows.value(); }
+ inline int cols() const { return m_blockCols.value(); }
+
+ inline int stride(void) const { return m_matrix.stride(); }
+
+ inline Scalar& coeffRef(int row, int col)
+ {
+ return m_matrix.const_cast_derived()
+ .coeffRef(row + m_startRow.value(), col + m_startCol.value());
+ }
+
+ inline const Scalar coeff(int row, int col) const
+ {
+ return m_matrix.coeff(row + m_startRow.value(), col + m_startCol.value());
+ }
+
+ inline Scalar& coeffRef(int index)
+ {
+ return m_matrix.const_cast_derived()
+ .coeffRef(m_startRow.value() + (RowsAtCompileTime == 1 ? 0 : index),
+ m_startCol.value() + (RowsAtCompileTime == 1 ? index : 0));
+ }
+
+ inline const Scalar coeff(int index) const
+ {
+ return m_matrix
+ .coeff(m_startRow.value() + (RowsAtCompileTime == 1 ? 0 : index),
+ m_startCol.value() + (RowsAtCompileTime == 1 ? index : 0));
+ }
+
+ protected:
+
+ const typename MatrixType::Nested m_matrix;
+ const ei_int_if_dynamic<MatrixType::RowsAtCompileTime == 1 ? 0 : Dynamic> m_startRow;
+ const ei_int_if_dynamic<MatrixType::ColsAtCompileTime == 1 ? 0 : Dynamic> m_startCol;
+ const ei_int_if_dynamic<RowsAtCompileTime> m_blockRows;
+ const ei_int_if_dynamic<ColsAtCompileTime> m_blockCols;
+
+};
+
+
+#endif // EIGEN_SPARSEBLOCK_H
Index: Eigen/Sparse
===================================================================
--- Eigen/Sparse (revision 853939)
+++ Eigen/Sparse (working copy)
@@ -13,6 +13,7 @@
#include "src/Sparse/SparseUtil.h"
#include "src/Sparse/SparseMatrixBase.h"
#include "src/Sparse/SparseArray.h"
+#include "src/Sparse/SparseBlock.h"
#include "src/Sparse/SparseMatrix.h"
#include "src/Sparse/HashMatrix.h"
#include "src/Sparse/LinkedVectorMatrix.h"