Eigen  5.0.1-dev+master
 
Loading...
Searching...
No Matches
BlockSparseMatrix.h
1// This file is part of Eigen, a lightweight C++ template library
2// for linear algebra.
3//
4// This Source Code Form is subject to the terms of the Mozilla
5// Public License v. 2.0. If a copy of the MPL was not distributed
6// with this file, You can obtain one at http://mozilla.org/MPL/2.0/.
7// SPDX-FileCopyrightText: The Eigen Authors
8// SPDX-License-Identifier: MPL-2.0
9
10#ifndef EIGEN_BLOCKSPARSEMATRIX_H
11#define EIGEN_BLOCKSPARSEMATRIX_H
12
13// IWYU pragma: private
14#include "./InternalHeaderCheck.h"
15
16#include <algorithm>
17#include <numeric>
18#include <utility>
19
20namespace Eigen {
21
22// Forward declarations
23template <typename, int, bool>
25template <typename, int, bool>
27template <typename Scalar_, int Options_, int BlockRows_, int BlockCols_, typename StorageIndex_>
29
31struct BlockSparse {};
32
35 static std::string debugName() { return "BlockSparseShape"; }
36};
37
38namespace internal {
39// Returns m.adjoint() when Conj==true, m.transpose() otherwise.
40// SFINAE overloads keep the return type concrete under C++14 (no if constexpr).
41template <bool Conj, typename T>
42std::enable_if_t<Conj, decltype(std::declval<const T&>().adjoint())> adjoint_if(const T& m) {
43 return m.adjoint();
44}
45
46template <bool Conj, typename T>
47std::enable_if_t<!Conj, decltype(std::declval<const T&>().transpose())> adjoint_if(const T& m) {
48 return m.transpose();
49}
50template <>
51struct storage_kind_to_evaluator_kind<BlockSparse> {
52 using Kind = IndexBased;
53};
54
55template <>
56struct storage_kind_to_shape<BlockSparse> {
57 using Shape = BlockSparseShape;
58};
59
60template <typename Scalar_, int Options_, int BlockRows_, int BlockCols_, typename StorageIndex_>
61struct traits<BlockSparseMatrix<Scalar_, Options_, BlockRows_, BlockCols_, StorageIndex_>> {
62 using Scalar = Scalar_;
63 using StorageIndex = StorageIndex_;
64 using StorageKind = BlockSparse;
65 using XprKind = MatrixXpr;
66
67 static constexpr Index RowsAtCompileTime = Dynamic;
68 static constexpr Index ColsAtCompileTime = Dynamic;
69 static constexpr Index MaxRowsAtCompileTime = Dynamic;
70 static constexpr Index MaxColsAtCompileTime = Dynamic;
71 static constexpr int Options = Options_;
72 static constexpr unsigned int Flags = Options_ | NestByRefBit | LvalueBit;
73};
74
75} // namespace internal
76
88template <typename Scalar_, int BlockRows_, int BlockCols_, int Options_ = ColMajor, typename StorageIndex_ = int>
89class BlockTriplet {
90 public:
91 using Scalar = Scalar_;
92 using StorageIndex = StorageIndex_;
94 using BlockMapType = Map<BlockType, Unaligned>;
95 using ConstBlockMapType = Map<const BlockType, Unaligned>;
96
97 static constexpr int BlockSize = BlockRows_ * BlockCols_;
98
99 BlockTriplet() = default;
100
101 BlockTriplet(StorageIndex blockRow, StorageIndex blockCol, const BlockType& block)
102 : m_row(blockRow), m_col(blockCol) {
103 BlockMapType{m_value} = block;
104 }
105
106 StorageIndex row() const { return m_row; }
107 StorageIndex col() const { return m_col; }
108 // Implicitly usable wherever a MatrixBase expression is expected.
109 ConstBlockMapType value() const { return ConstBlockMapType(m_value); }
110
111 private:
112 StorageIndex m_row = 0;
113 StorageIndex m_col = 0;
114 // Flat array avoids the alignment padding that a Matrix<> member would incur.
115 Scalar m_value[BlockSize];
116};
117
158template <typename Scalar_, int Options_, int BlockRows_, int BlockCols_, typename StorageIndex_ = int>
159class BlockSparseMatrix
160 : public EigenBase<BlockSparseMatrix<Scalar_, Options_, BlockRows_, BlockCols_, StorageIndex_>> {
161 EIGEN_STATIC_ASSERT(BlockRows_ >= 1, BLOCKROWS_MUST_BE_A_POSITIVE_COMPILE_TIME_SIZE)
162 EIGEN_STATIC_ASSERT(BlockCols_ >= 1, BLOCKCOLS_MUST_BE_A_POSITIVE_COMPILE_TIME_SIZE)
163 EIGEN_STATIC_ASSERT(std::is_integral<StorageIndex_>::value&& std::is_signed<StorageIndex_>::value,
164 STORAGEINDEX_MUST_BE_A_SIGNED_INTEGRAL_TYPE)
165 // Eigen's Matrix<> requires: a column vector (Cols==1, Rows>1) must be ColMajor;
166 // a row vector (Rows==1, Cols>1) must be RowMajor. Guard those cases here so
167 // the error fires at BlockSparseMatrix instantiation rather than inside BlockType.
168 EIGEN_STATIC_ASSERT(!(BlockCols_ == 1 && BlockRows_ != 1 && bool(Options_ & RowMajorBit)),
169 INVALID_MATRIX_TEMPLATE_PARAMETERS)
170 EIGEN_STATIC_ASSERT(!(BlockRows_ == 1 && BlockCols_ != 1 && !bool(Options_ & RowMajorBit)),
171 INVALID_MATRIX_TEMPLATE_PARAMETERS)
172
173 public:
174 // -------------------------------------------------------------------------
175 // Type aliases & compile-time constants
176 // -------------------------------------------------------------------------
177 using Scalar = Scalar_;
178 using StorageIndex = StorageIndex_;
181
182 static constexpr int Options = Options_;
183 static constexpr Index BlockRows = BlockRows_;
184 static constexpr Index BlockCols = BlockCols_;
185 static constexpr bool IsRowMajor = Options_ & RowMajorBit;
186 static constexpr Index BlockSize = BlockRows_ * BlockCols_;
187
188 // If one block occupies a power-of-two number of bytes, and the values array
189 // is Eigen-allocated (guaranteed aligned to EIGEN_MAX_ALIGN_BYTES), then every
190 // block pointer is aligned to min(BlockBytes, EIGEN_MAX_ALIGN_BYTES).
191 static constexpr std::size_t BlockBytes = std::size_t(BlockSize) * sizeof(Scalar);
192 static constexpr int BlockMapAlignment = ((BlockBytes & (BlockBytes - 1)) == 0 && BlockBytes >= 8)
193 ? int(numext::mini(BlockBytes, std::size_t(EIGEN_MAX_ALIGN_BYTES)))
194 : 0;
195
196 using BlockMap = Map<BlockType, BlockMapAlignment>;
197 using ConstBlockMap = Map<const BlockType, BlockMapAlignment>;
198
199 // -------------------------------------------------------------------------
200 // Constructors / copy / move
201 // -------------------------------------------------------------------------
202
204 BlockSparseMatrix() = default;
205
208 : m_blockOuterSize(IsRowMajor ? blockRows : blockCols), m_blockInnerSize(IsRowMajor ? blockCols : blockRows) {}
209
210 // -------------------------------------------------------------------------
211 // Dimensions
212 // -------------------------------------------------------------------------
213
215 Index rows() const noexcept { return (IsRowMajor ? m_blockOuterSize : m_blockInnerSize) * BlockRows_; }
217 Index cols() const noexcept { return (IsRowMajor ? m_blockInnerSize : m_blockOuterSize) * BlockCols_; }
218
220 Index blockRows() const { return IsRowMajor ? m_blockOuterSize : m_blockInnerSize; }
222 Index blockCols() const { return IsRowMajor ? m_blockInnerSize : m_blockOuterSize; }
223
225 Index blockOuterSize() const { return m_blockOuterSize; }
227 Index blockInnerSize() const { return m_blockInnerSize; }
228
230 Index outerSize() const { return IsRowMajor ? rows() : cols(); }
232 Index innerSize() const { return IsRowMajor ? cols() : rows(); }
233
235 Index nonZeroBlocks() const { return m_outerIndex(m_blockOuterSize); }
237 Index nonZeros() const { return nonZeroBlocks() * BlockSize; }
239 Index allocatedBlocks() const { return Index(m_innerIndex.size()); }
240
241 // -------------------------------------------------------------------------
242 // Raw pointer access (for interoperability)
243 // -------------------------------------------------------------------------
244 const StorageIndex* outerIndexPtr() const { return m_outerIndex.data(); }
245 StorageIndex* outerIndexPtr() { return m_outerIndex.data(); }
246 const StorageIndex* innerIndexPtr() const { return m_innerIndex.data(); }
247 StorageIndex* innerIndexPtr() { return m_innerIndex.data(); }
248 const Scalar* valuePtr() const { return m_values.data(); }
249 Scalar* valuePtr() { return m_values.data(); }
250
251 // -------------------------------------------------------------------------
252 // Block access by sequential nonzero index
253 // -------------------------------------------------------------------------
254
256 ConstBlockMap blockRef(Index k) const { return ConstBlockMap(m_values.data() + k * BlockSize); }
258 BlockMap blockRef(Index k) { return BlockMap(m_values.data() + k * BlockSize); }
259
260 // -------------------------------------------------------------------------
261 // Inner iterator over blocks within one outer vector
262 // -------------------------------------------------------------------------
263
269 class InnerIterator {
270 public:
271 EIGEN_STRONG_INLINE InnerIterator(const BlockSparseMatrix& mat, Index outer)
272 : m_mat(mat), m_id(mat.m_outerIndex(outer)), m_end(mat.m_outerIndex(outer + 1)), m_outer(outer) {}
273
274 EIGEN_STRONG_INLINE operator bool() const { return m_id < m_end; }
275 EIGEN_STRONG_INLINE InnerIterator& operator++() {
276 ++m_id;
277 return *this;
278 }
279
281 EIGEN_STRONG_INLINE Index outer() const { return m_outer; }
283 EIGEN_STRONG_INLINE Index index() const { return m_mat.m_innerIndex(m_id); }
285 EIGEN_STRONG_INLINE Index blockRow() const { return IsRowMajor ? m_outer : index(); }
287 EIGEN_STRONG_INLINE Index blockCol() const { return IsRowMajor ? index() : m_outer; }
288
290 EIGEN_STRONG_INLINE ConstBlockMap value() const { return m_mat.blockRef(m_id); }
292 EIGEN_STRONG_INLINE BlockMap valueRef() {
293 return BlockMap(const_cast<Scalar*>(m_mat.m_values.data()) + m_id * BlockSize);
294 }
295
296 private:
297 const BlockSparseMatrix& m_mat;
298 Index m_id;
299 Index m_end;
300 Index m_outer;
301 };
302
303 // -------------------------------------------------------------------------
304 // Resize / clear
305 // -------------------------------------------------------------------------
306
310 m_blockOuterSize = IsRowMajor ? blockRows : blockCols;
311 m_blockInnerSize = IsRowMajor ? blockCols : blockRows;
312 m_outerIndex.resize(m_blockOuterSize + 1);
313 m_outerIndex.setZero();
314 }
315
317 void setZero() {
318 m_outerIndex.resize(m_blockOuterSize + 1);
319 m_outerIndex.setZero();
320 }
321
324 void reserve(Index n) {
325 if (n > Index(m_innerIndex.size())) conservativeResizeBlockStorage_(n);
326 }
327
329 void squeeze() {
330 Index nnz = nonZeroBlocks();
331 if (nnz < Index(m_innerIndex.size())) conservativeResizeBlockStorage_(nnz);
332 }
333
339 void setIdentity() {
340 EIGEN_STATIC_ASSERT(BlockRows_ == BlockCols_, THIS_METHOD_IS_ONLY_FOR_SQUARE_BLOCK_MATRICES)
341 Index n = (std::min)(m_blockOuterSize, m_blockInnerSize);
342 m_outerIndex.resize(m_blockOuterSize + 1);
343 resizeBlockStorage_(n);
344 for (Index i = 0; i <= m_blockOuterSize; ++i) m_outerIndex(i) = StorageIndex((std::min)(i, n));
345 for (StorageIndex i = 0; i < n; ++i) {
346 m_innerIndex(i) = i;
347 blockRef(i).setIdentity();
348 }
349 }
350
357 void setFromOuterInner(Index blockRows, Index blockCols, Index nnzBlocks, const StorageIndex_* outerPtr,
358 const StorageIndex_* innerPtr) {
359 m_blockOuterSize = IsRowMajor ? blockRows : blockCols;
360 m_blockInnerSize = IsRowMajor ? blockCols : blockRows;
361 m_outerIndex = Map<const decltype(m_outerIndex)>(outerPtr, m_blockOuterSize + 1);
362 m_innerIndex = Map<const decltype(m_innerIndex)>(innerPtr, nnzBlocks);
363 resizeBlockStorage_(nnzBlocks);
364 m_values.setZero();
365 }
366
367 // -------------------------------------------------------------------------
368 // Assembly
369 // -------------------------------------------------------------------------
370
381 template <typename InputIterator>
382 void setFromTriplets(InputIterator begin, InputIterator end);
383
384 // -------------------------------------------------------------------------
385 // Conversion to / from SparseMatrix
386 // -------------------------------------------------------------------------
387
395
406
409
410 // -------------------------------------------------------------------------
411 // Element access
412 // -------------------------------------------------------------------------
413
415 Scalar coeff(Index row, Index col) const {
416 eigen_assert(row >= 0 && row < rows() && col >= 0 && col < cols());
417 Index bOuter = IsRowMajor ? (row / BlockRows_) : (col / BlockCols_);
418 Index bInner = IsRowMajor ? (col / BlockCols_) : (row / BlockRows_);
419 Index localRow = row % BlockRows_;
420 Index localCol = col % BlockCols_;
421 const StorageIndex* beg = m_innerIndex.data() + m_outerIndex(bOuter);
422 const StorageIndex* fin = m_innerIndex.data() + m_outerIndex(bOuter + 1);
423 const StorageIndex* it = std::lower_bound(beg, fin, StorageIndex(bInner));
424 if (it == fin || *it != bInner) return Scalar(0);
425 return blockRef(static_cast<Index>(it - m_innerIndex.data()))(localRow, localCol);
426 }
427
436 constexpr Index OuterB = IsRowMajor ? BlockRows_ : BlockCols_;
437 constexpr Index InnerB = IsRowMajor ? BlockCols_ : BlockRows_;
438 const Index diagSize = numext::mini(rows(), cols());
440
441 for (Index out = 0; out < m_blockOuterSize; ++out) {
442 const Index scalarOuterBegin = out * OuterB;
443 if (scalarOuterBegin >= diagSize) break;
444 const Index scalarOuterEnd = numext::mini(scalarOuterBegin + OuterB, diagSize);
445
446 // Group consecutive scalar positions that share the same inner block, then
447 // binary-search once per group rather than once per scalar element.
448 // For square blocks this loop runs exactly once per outer slice.
449 Index i = scalarOuterBegin;
450 while (i < scalarOuterEnd) {
451 const Index bInner = i / InnerB;
452 const Index groupEnd = numext::mini((bInner + 1) * InnerB, scalarOuterEnd);
453
454 const StorageIndex* beg = m_innerIndex.data() + m_outerIndex(out);
455 const StorageIndex* fin = m_innerIndex.data() + m_outerIndex(out + 1);
456 const StorageIndex* it = std::lower_bound(beg, fin, StorageIndex(bInner));
457 if (it != fin && *it == StorageIndex(bInner)) {
458 const ConstBlockMap blk = blockRef(static_cast<Index>(it - m_innerIndex.data()));
459 for (Index j = i; j < groupEnd; ++j) {
460 const Index localRow = IsRowMajor ? (j % OuterB) : (j % InnerB);
461 const Index localCol = IsRowMajor ? (j % InnerB) : (j % OuterB);
462 diag(j) = blk(localRow, localCol);
463 }
464 }
465 i = groupEnd;
466 }
467 }
468 return diag;
469 }
470
471 // -------------------------------------------------------------------------
472 // Arithmetic
473 // -------------------------------------------------------------------------
474
476 BlockSparseMatrix operator+(const BlockSparseMatrix& other) const { return disjunctionWith_(other, AddOp_{}); }
477
479 BlockSparseMatrix operator-(const BlockSparseMatrix& other) const { return disjunctionWith_(other, SubOp_{}); }
480
482 BlockSparseMatrix cwiseProduct(const BlockSparseMatrix& other) const {
483 return conjunctionWith_(other, CwiseMulOp_{});
484 }
485
487 template <typename ScalarFunc>
488 BlockSparseMatrix unaryExpr(ScalarFunc func) const {
489 return withValues_([&func](const auto& v) { return v.unaryExpr(func); });
490 }
491
501 template <typename ScalarFunc>
502 BlockSparseMatrix disjunctionExpr(const BlockSparseMatrix& other, ScalarFunc func) const {
503 return disjunctionWith_(other, DisjExprAdapter_<ScalarFunc>{func});
504 }
505
508 template <typename ScalarFunc>
509 BlockSparseMatrix conjunctionExpr(const BlockSparseMatrix& other, ScalarFunc func) const {
510 return conjunctionWith_(other, [&func](const auto& a, const auto& b) { return a.binaryExpr(b, func); });
511 }
512
514 BlockSparseMatrix operator-() const {
515 return withValues_([](const auto& v) { return -v; });
516 }
517
518 BlockSparseMatrix& operator+=(const BlockSparseMatrix& other) { return *this = *this + other; }
519 BlockSparseMatrix& operator-=(const BlockSparseMatrix& other) { return *this = *this - other; }
520
522 BlockSparseMatrix operator*(const Scalar& s) const {
523 return withValues_([&s](const auto& v) { return v * s; });
524 }
525 BlockSparseMatrix& operator*=(const Scalar& s) {
526 m_values.head(nonZeros()) *= s;
527 return *this;
528 }
529 BlockSparseMatrix operator/(const Scalar& s) const {
530 return withValues_([&s](const auto& v) { return v / s; });
531 }
532 BlockSparseMatrix& operator/=(const Scalar& s) {
533 m_values.head(nonZeros()) /= s;
534 return *this;
535 }
536
538 friend BlockSparseMatrix operator*(const Scalar& s, const BlockSparseMatrix& m) { return m * s; }
539
556 template <typename OtherDerived>
558 EIGEN_STATIC_ASSERT(
559 (std::is_same<Scalar, typename OtherDerived::Scalar>::value),
560 YOU_MIXED_DIFFERENT_NUMERIC_TYPES__YOU_NEED_TO_USE_THE_CAST_METHOD_OF_MATRIXBASE_TO_CAST_NUMERIC_TYPES_EXPLICITLY)
562 }
563
574 template <typename OtherDerived>
576 const BlockSparseMatrix& bsm) {
577 EIGEN_STATIC_ASSERT(
578 (std::is_same<Scalar_, typename OtherDerived::Scalar>::value),
579 YOU_MIXED_DIFFERENT_NUMERIC_TYPES__YOU_NEED_TO_USE_THE_CAST_METHOD_OF_MATRIXBASE_TO_CAST_NUMERIC_TYPES_EXPLICITLY)
581 }
582
595 template <int RhsBlockCols>
598
599 // -------------------------------------------------------------------------
600 // Approximate equality (useful for testing)
601 // -------------------------------------------------------------------------
602 bool isApprox(const BlockSparseMatrix& other,
603 const typename NumTraits<Scalar>::Real& prec = NumTraits<Scalar>::dummy_precision()) const {
604 using Comparison = internal::sparse_approx_comparison<Scalar>;
605 using Wide = typename Comparison::Wide;
606 // Frobenius-norm comparison, matching SparseMatrixBase::isApprox semantics
607 // but computed directly from the block values — no scalar-level SparseMatrix
608 // materialization of either operand while the squared norms are in range.
609 // Explicit zero blocks contribute 0 to every norm, so the result is
610 // independent of structural differences.
611 const auto squaredNorm = [](const BlockSparseMatrix& m) {
612 return m.m_values.head(m.nonZeros()).matrix().template cast<Wide>().squaredNorm();
613 };
614 return Comparison::compare(
615 squaredNorm(*this), squaredNorm(other), nonZeros() + other.nonZeros(), prec,
616 [&] { return squaredNorm(*this - other); }, [&] { return toSparse().isApprox(other.toSparse(), prec); });
617 }
618
619 // -------------------------------------------------------------------------
620 // Transpose / adjoint
621 // -------------------------------------------------------------------------
622
625 BlockSparseMatrix<Scalar_, Options_, BlockCols_, BlockRows_, StorageIndex_> transpose() const;
626
629 BlockSparseMatrix<Scalar_, Options_, BlockCols_, BlockRows_, StorageIndex_> adjoint() const;
630
631 // -------------------------------------------------------------------------
632 // View factories
633 // -------------------------------------------------------------------------
634
645 template <int Mode, bool DiagIsTriangular = false>
646 BlockSparseTriangularView<BlockSparseMatrix, Mode, DiagIsTriangular> triangularView() const {
647 return BlockSparseTriangularView<BlockSparseMatrix, Mode, DiagIsTriangular>(*this);
648 }
649
666 template <int UpLo, bool DiagIsSelfAdjoint = false>
667 BlockSparseSelfAdjointView<BlockSparseMatrix, UpLo, DiagIsSelfAdjoint> selfadjointView() const {
668 EIGEN_STATIC_ASSERT(BlockRows_ == BlockCols_, THIS_METHOD_IS_ONLY_FOR_SQUARE_BLOCK_MATRICES)
669 return BlockSparseSelfAdjointView<BlockSparseMatrix, UpLo, DiagIsSelfAdjoint>(*this);
670 }
671
672 private:
673 struct AddOp_ {
674 template <typename A, typename B>
675 BlockType operator()(const A& a, const B& b) const {
676 return a + b;
677 }
678 template <typename A>
679 BlockType lhs(const A& a) const {
680 return a;
681 }
682 template <typename B>
683 BlockType rhs(const B& b) const {
684 return b;
685 }
686 };
687
688 struct SubOp_ {
689 template <typename A, typename B>
690 BlockType operator()(const A& a, const B& b) const {
691 return a - b;
692 }
693 template <typename A>
694 BlockType lhs(const A& a) const {
695 return a;
696 }
697 template <typename B>
698 BlockType rhs(const B& b) const {
699 return -b;
700 }
701 };
702
703 // Scalar-to-block adapter for disjunctionExpr: translates scalar functor with lhs/rhs methods
704 // to the block level.
705 template <typename ScalarFunc>
706 struct DisjExprAdapter_ {
707 ScalarFunc func_;
708 template <typename A, typename B>
709 BlockType operator()(const A& a, const B& b) const {
710 return a.binaryExpr(b, func_);
711 }
712 template <typename A>
713 BlockType lhs(const A& a) const {
714 return a.unaryExpr([this](const Scalar& x) { return func_.lhs(x); });
715 }
716 template <typename B>
717 BlockType rhs(const B& b) const {
718 return b.unaryExpr([this](const Scalar& x) { return func_.rhs(x); });
719 }
720 };
721
722 struct CwiseMulOp_ {
723 template <typename A, typename B>
724 BlockType operator()(const A& a, const B& b) const {
725 return a.cwiseProduct(b);
726 }
727 };
728
729 // Returns a copy with the same sparsity structure but m_values replaced by f(m_values).
730 // f receives the flat Eigen Array of the logical (non-zero) coefficients and returns any
731 // compatible expression. Only the structure is copied — the source values are never
732 // duplicated, and unused tail capacity is neither copied nor evaluated.
733 template <typename F>
734 BlockSparseMatrix withValues_(F f) const {
735 Index nnz = nonZeroBlocks();
736 BlockSparseMatrix result(blockRows(), blockCols());
737 result.m_outerIndex = m_outerIndex;
738 result.m_innerIndex = m_innerIndex.head(nnz);
739 result.m_values = f(m_values.head(nnz * BlockSize));
740 return result;
741 }
742
743 // Disjunction (union-pattern): result has a block wherever *this OR other has one.
744 // lhs-only: block copied from *this unchanged
745 // rhs-only: op(b) — unary overload of op
746 // both: op(a, b) — binary overload of op
747 template <typename Op>
748 BlockSparseMatrix disjunctionWith_(const BlockSparseMatrix& other, Op op) const {
749 eigen_assert(blockRows() == other.blockRows() && blockCols() == other.blockCols() &&
750 "BlockSparseMatrix size mismatch");
751 BlockSparseMatrix result(blockRows(), blockCols());
752 result.resizeBlockStorage_(nonZeroBlocks() + other.nonZeroBlocks());
753 Index nnz = 0;
754 for (Index j = 0; j < m_blockOuterSize; ++j) {
755 result.m_outerIndex(j) = StorageIndex_(nnz);
756 Index aId = m_outerIndex(j);
757 Index aEnd = m_outerIndex(j + 1);
758 Index bId = other.m_outerIndex(j);
759 Index bEnd = other.m_outerIndex(j + 1);
760 while (aId < aEnd || bId < bEnd) {
761 bool hasA = aId < aEnd;
762 bool hasB = bId < bEnd;
763 Index aInner = hasA ? Index(m_innerIndex(aId)) : -1;
764 Index bInner = hasB ? Index(other.m_innerIndex(bId)) : -1;
765 // Write the result block in place; the op overloads return a BlockType,
766 // which is assigned straight into the result's storage Map.
767 if (hasA && (!hasB || aInner < bInner)) {
768 result.m_innerIndex(nnz) = StorageIndex_(aInner);
769 result.blockRef(nnz) = op.lhs(blockRef(aId++));
770 } else if (hasB && (!hasA || bInner < aInner)) {
771 result.m_innerIndex(nnz) = StorageIndex_(bInner);
772 result.blockRef(nnz) = op.rhs(other.blockRef(bId++));
773 } else {
774 result.m_innerIndex(nnz) = StorageIndex_(aInner);
775 result.blockRef(nnz) = op(blockRef(aId++), other.blockRef(bId++));
776 }
777 ++nnz;
778 }
779 }
780 result.m_outerIndex(m_blockOuterSize) = StorageIndex_(nnz);
781 result.conservativeResizeBlockStorage_(nnz);
782 return result;
783 }
784
785 // Conjunction (intersection-pattern): result has a block only where *this AND other both have one.
786 template <typename BinaryOp>
787 BlockSparseMatrix conjunctionWith_(const BlockSparseMatrix& other, BinaryOp func) const {
788 eigen_assert(blockRows() == other.blockRows() && blockCols() == other.blockCols() &&
789 "BlockSparseMatrix size mismatch");
790 BlockSparseMatrix result(blockRows(), blockCols());
791 result.resizeBlockStorage_((std::min)(nonZeroBlocks(), other.nonZeroBlocks()));
792 Index nnz = 0;
793 for (Index j = 0; j < m_blockOuterSize; ++j) {
794 result.m_outerIndex(j) = StorageIndex_(nnz);
795 Index aId = m_outerIndex(j);
796 Index aEnd = m_outerIndex(j + 1);
797 Index bId = other.m_outerIndex(j);
798 Index bEnd = other.m_outerIndex(j + 1);
799 while (aId < aEnd && bId < bEnd) {
800 Index aInner = m_innerIndex(aId);
801 Index bInner = other.m_innerIndex(bId);
802 if (aInner < bInner) {
803 ++aId;
804 } else if (bInner < aInner) {
805 ++bId;
806 } else {
807 result.m_innerIndex(nnz) = StorageIndex_(aInner);
808 result.blockRef(nnz) = func(blockRef(aId++), other.blockRef(bId++));
809 ++nnz;
810 }
811 }
812 }
813 result.m_outerIndex(m_blockOuterSize) = StorageIndex_(nnz);
814 result.conservativeResizeBlockStorage_(nnz);
815 return result;
816 }
817
818 template <bool Conjugate>
819 BlockSparseMatrix<Scalar_, Options_, BlockCols_, BlockRows_, StorageIndex_> transposeImpl() const;
820
821 // Resize both block storage arrays non-conservatively and update the capacity counter.
822 void resizeBlockStorage_(Index n) {
823 m_innerIndex.resize(n);
824 m_values.resize(n * BlockSize);
825 }
826
827 void conservativeResizeBlockStorage_(Index n) {
828 m_innerIndex.conservativeResize(n);
829 m_values.conservativeResize(n * BlockSize);
830 }
831
832 // -------------------------------------------------------------------------
833 // Storage
834 // -------------------------------------------------------------------------
835 Index m_blockOuterSize = 0; // block-cols (ColMajor) or block-rows (RowMajor)
836 Index m_blockInnerSize = 0; // block-rows (ColMajor) or block-cols (RowMajor)
837
838 Array<StorageIndex, Dynamic, 1> m_outerIndex = // size: m_blockOuterSize + 1
839 decltype(m_outerIndex)::Zero(m_blockOuterSize + 1);
840 Array<StorageIndex, Dynamic, 1> m_innerIndex;
841 // Block values stored consecutively; block k occupies
842 // m_values[k*BlockSize .. (k+1)*BlockSize - 1].
843 Array<Scalar, Dynamic, 1> m_values;
844
845 // -------------------------------------------------------------------------
846 // MultiInnerIterator
847 //
848 // Simultaneously walks BlockOuterSize_ consecutive outer vectors of a
849 // compressed SparseMatrix, yielding scalar entries one at a time in
850 // non-decreasing inner-index order. On each step the sub-iterator with
851 // the smallest current inner index is the "active" one.
852 //
853 // BlockOuterSize_ is BlockCols_ for ColMajor (one block-column at a time)
854 // and BlockRows_ for RowMajor (one block-row at a time).
855 // -------------------------------------------------------------------------
856 template <typename SparseMatrixType>
857 class MultiInnerIterator {
858 using StorageIndex = typename SparseMatrixType::StorageIndex;
859 static constexpr int BlockOuterSize_ = IsRowMajor ? BlockRows_ : BlockCols_;
860
861 public:
862 MultiInnerIterator(const SparseMatrixType& mat, Index outerBase)
863 : m_outerPtr(mat.outerIndexPtr()),
864 m_innerPtr(mat.innerIndexPtr()),
865 m_valuePtr(mat.valuePtr()),
866 m_outerBase(outerBase) {
867 for (int k = 0; k < BlockOuterSize_; ++k) m_pos[k] = m_outerPtr[outerBase + k];
868 advance();
869 }
870
871 EIGEN_STRONG_INLINE operator bool() const { return m_valid; }
872
873 EIGEN_STRONG_INLINE MultiInnerIterator& operator++() {
874 ++m_pos[m_active];
875 advance();
876 return *this;
877 }
878
879 // Absolute outer index of the current entry.
880 EIGEN_STRONG_INLINE Index outer() const { return m_outerBase + m_active; }
881 // Inner index of the current entry.
882 EIGEN_STRONG_INLINE StorageIndex index() const { return m_innerPtr[m_pos[m_active]]; }
883 // Scalar value of the current entry.
884 EIGEN_STRONG_INLINE Scalar value() const { return m_valuePtr[m_pos[m_active]]; }
885
886 private:
887 // Find the sub-iterator with the smallest inner index.
888 void advance() {
889 m_valid = false;
890 for (int k = 0; k < BlockOuterSize_; ++k) {
891 if (m_pos[k] < m_outerPtr[m_outerBase + k + 1]) {
892 if (!m_valid || m_innerPtr[m_pos[k]] < m_innerPtr[m_pos[m_active]]) {
893 m_active = k;
894 m_valid = true;
895 }
896 }
897 }
898 }
899
900 const StorageIndex* m_outerPtr;
901 const StorageIndex* m_innerPtr;
902 const Scalar* m_valuePtr;
903 Index m_outerBase;
904 StorageIndex m_pos[BlockOuterSize_];
905 int m_active = 0;
906 bool m_valid = false;
907 };
908
909 // Allow other instantiations of BlockSparseMatrix to access private members
910 // (needed by operator*).
911 template <typename, int, int, int, typename>
912 friend class BlockSparseMatrix;
913 template <typename, int, bool>
914 friend class BlockSparseTriangularView;
915 template <typename, int, bool>
916 friend class BlockSparseSelfAdjointView;
917};
918
919// =============================================================================
920// Out-of-line method definitions
921// =============================================================================
922
923// -----------------------------------------------------------------------------
924// setFromTriplets
925// -----------------------------------------------------------------------------
926
927template <typename Scalar_, int Options_, int BlockRows_, int BlockCols_, typename StorageIndex_>
928template <typename InputIterator>
930 InputIterator end) {
931 Index n = static_cast<Index>(std::distance(begin, end));
932
933 // Copy triplet coordinates and block values into Eigen arrays.
934 Array<StorageIndex, Dynamic, 1> tOuter(n), tInner(n);
935 Array<Scalar, Dynamic, 1> tValues(n * BlockSize);
936
937 Index k = 0;
938 for (InputIterator it = begin; it != end; ++it, ++k) {
939 eigen_assert(it->row() >= 0 && it->row() < blockRows() && "setFromTriplets: block row out of range");
940 eigen_assert(it->col() >= 0 && it->col() < blockCols() && "setFromTriplets: block col out of range");
941 tOuter(k) = IsRowMajor ? StorageIndex(it->row()) : StorageIndex(it->col());
942 tInner(k) = IsRowMajor ? StorageIndex(it->col()) : StorageIndex(it->row());
943 BlockMap(tValues.data() + k * BlockSize) = it->value();
944 }
945
946 // Order the triplet indices by (outer, inner) using a stable LSD radix sort:
947 // pass 1 buckets by inner, pass 2 by outer. This runs in
948 // O(n + blockInnerSize + blockOuterSize) with sequential writes, avoiding the
949 // cache-unfriendly indirect comparison sort.
950 Array<Index, Dynamic, 1> order(n), scratch(n);
951 {
952 Array<Index, Dynamic, 1> count = Array<Index, Dynamic, 1>::Zero(m_blockInnerSize + 1);
953 for (Index i = 0; i < n; ++i) count(tInner(i) + 1)++;
954 for (Index i = 0; i < m_blockInnerSize; ++i) count(i + 1) += count(i);
955 for (Index i = 0; i < n; ++i) order(count(tInner(i))++) = i;
956 }
957 {
958 Array<Index, Dynamic, 1> count = Array<Index, Dynamic, 1>::Zero(m_blockOuterSize + 1);
959 for (Index i = 0; i < n; ++i) count(tOuter(i) + 1)++;
960 for (Index i = 0; i < m_blockOuterSize; ++i) count(i + 1) += count(i);
961 for (Index i = 0; i < n; ++i) {
962 Index idx = order(i);
963 scratch(count(tOuter(idx))++) = idx;
964 }
965 order.swap(scratch);
966 }
967
968 // Reset and pre-allocate (worst case: all n triplets are distinct blocks).
969 m_outerIndex.resize(m_blockOuterSize + 1);
970 m_outerIndex.setZero();
971 resizeBlockStorage_(n);
972
973 Index nnz = 0;
974 k = 0;
975 while (k < n) {
976 Index pi = order(k);
977 StorageIndex outer = tOuter(pi);
978 StorageIndex inner = tInner(pi);
979
980 BlockType block = ConstBlockMap(tValues.data() + pi * BlockSize);
981 ++k;
982
983 // Accumulate duplicate entries at the same (outer, inner) position.
984 while (k < n) {
985 Index pk = order(k);
986 if (tOuter(pk) != outer || tInner(pk) != inner) break;
987 block += ConstBlockMap(tValues.data() + pk * BlockSize);
988 ++k;
989 }
990
991 m_innerIndex(nnz) = inner;
992 blockRef(nnz) = block;
993 m_outerIndex(outer + 1)++;
994 ++nnz;
995 }
996
997 // Trim to actual number of unique blocks.
998 conservativeResizeBlockStorage_(nnz);
999
1000 // Convert per-outer block counts to prefix sums.
1001 for (Index j = 0; j < m_blockOuterSize; ++j) {
1002 m_outerIndex(j + 1) += m_outerIndex(j);
1003 }
1004}
1005
1006// -----------------------------------------------------------------------------
1007// toSparse
1008// -----------------------------------------------------------------------------
1009
1010template <typename Scalar_, int Options_, int BlockRows_, int BlockCols_, typename StorageIndex_>
1014 result.reserve(nonZeroBlocks() * BlockSize);
1015
1016 if (!IsRowMajor) {
1017 // ColMajor: outer = block-column j. Emit scalar columns j*BlockCols+c
1018 // in order c = 0..BlockCols-1. Within each scalar column, blocks are
1019 // sorted by bi (block-row), so scalar rows bi*BlockRows+r are increasing.
1020 for (Index j = 0; j < m_blockOuterSize; ++j) {
1021 for (Index c = 0; c < BlockCols_; ++c) {
1022 result.startVec(j * BlockCols_ + c);
1023 for (Index id = m_outerIndex(j); id < m_outerIndex(j + 1); ++id) {
1024 Index bi = m_innerIndex(id);
1025 ConstBlockMap blk = blockRef(id);
1026 for (Index r = 0; r < BlockRows_; ++r) {
1027 result.insertBack(bi * BlockRows_ + r, j * BlockCols_ + c) = blk(r, c);
1028 }
1029 }
1030 }
1031 }
1032 } else {
1033 // RowMajor: outer = block-row bi. Emit scalar rows bi*BlockRows+r
1034 // in order r = 0..BlockRows-1. Within each scalar row, blocks are
1035 // sorted by j (block-col), so scalar cols j*BlockCols+c are increasing.
1036 for (Index bi = 0; bi < m_blockOuterSize; ++bi) {
1037 for (Index r = 0; r < BlockRows_; ++r) {
1038 result.startVec(bi * BlockRows_ + r);
1039 for (Index id = m_outerIndex(bi); id < m_outerIndex(bi + 1); ++id) {
1040 Index j = m_innerIndex(id);
1041 ConstBlockMap blk = blockRef(id);
1042 for (Index c = 0; c < BlockCols_; ++c) {
1043 result.insertBack(bi * BlockRows_ + r, j * BlockCols_ + c) = blk(r, c);
1044 }
1045 }
1046 }
1047 }
1048 }
1049
1050 result.finalize();
1051 return result;
1052}
1053
1054// -----------------------------------------------------------------------------
1055// fromSparse
1056// -----------------------------------------------------------------------------
1057
1058template <typename Scalar_, int Options_, int BlockRows_, int BlockCols_, typename StorageIndex_>
1062 eigen_assert(sp.rows() % BlockRows_ == 0 && "matrix rows not divisible by BlockRows");
1063 eigen_assert(sp.cols() % BlockCols_ == 0 && "matrix cols not divisible by BlockCols");
1064 eigen_assert(sp.isCompressed() && "fromSparse requires a compressed SparseMatrix");
1065
1066 Index bRows = sp.rows() / BlockRows_;
1067 Index bCols = sp.cols() / BlockCols_;
1068
1069 // BlockOuterSize: how many consecutive outer vectors form one block-outer strip.
1070 // BlockInnerSize: the inner dimension of each block.
1071 constexpr Index BlockOuterSize = IsRowMajor ? BlockRows_ : BlockCols_;
1072 constexpr Index BlockInnerSize = IsRowMajor ? BlockCols_ : BlockRows_;
1073 constexpr StorageIndex_ kEmptyIndex = -1;
1074
1076
1077 BlockSparseMatrix result(bRows, bCols);
1078
1079 // Pass 1: count the number of unique block-inner indices per block-outer,
1080 // by scanning each group of BlockOuterSize consecutive outer vectors together.
1081 for (Index outerBlock = 0; outerBlock < result.m_blockOuterSize; ++outerBlock) {
1082 StorageIndex_ prevInnerBlock = kEmptyIndex;
1083 for (MultiInnerIterator<SpMat> it(sp, outerBlock * BlockOuterSize); it; ++it) {
1084 StorageIndex_ innerBlock = it.index() / StorageIndex_(BlockInnerSize);
1085 if (innerBlock != prevInnerBlock) {
1086 result.m_outerIndex(outerBlock + 1)++;
1087 prevInnerBlock = innerBlock;
1088 }
1089 }
1090 }
1091
1092 // Prefix sum → result.m_outerIndex becomes the standard CSC/CSR outer pointer.
1093 for (Index j = 0; j < result.m_blockOuterSize; ++j) result.m_outerIndex(j + 1) += result.m_outerIndex(j);
1094
1095 Index nBlocks = result.m_outerIndex(result.m_blockOuterSize);
1096 result.resizeBlockStorage_(nBlocks);
1097 result.m_values.setZero();
1098
1099 // Pass 2: scatter each scalar entry directly into its position within the
1100 // pre-zeroed block value array.
1101 for (Index outerBlock = 0; outerBlock < result.m_blockOuterSize; ++outerBlock) {
1102 Index blockId = result.m_outerIndex(outerBlock) - 1; // incremented on first new block
1103 StorageIndex_ prevInnerBlock = kEmptyIndex;
1104
1105 for (MultiInnerIterator<SpMat> it(sp, outerBlock * BlockOuterSize); it; ++it) {
1106 Index absOuter = it.outer(); // absolute outer index in sp
1107 StorageIndex_ innerIdx = it.index(); // inner index in sp
1108 StorageIndex_ innerBlock = innerIdx / StorageIndex_(BlockInnerSize);
1109
1110 if (innerBlock != prevInnerBlock) {
1111 ++blockId;
1112 result.m_innerIndex(blockId) = innerBlock;
1113 prevInnerBlock = innerBlock;
1114 }
1115
1116 // Scatter into block storage (layout matches the BSM's Options_).
1117 // ColMajor blocks: col * BlockRows_ + row = localOuter * BlockInnerSize + localInner
1118 // RowMajor blocks: row * BlockCols_ + col = localOuter * BlockInnerSize + localInner
1119 Index localOuter = absOuter % BlockOuterSize;
1120 Index localInner = innerIdx % BlockInnerSize;
1121 Index offset = localOuter * BlockInnerSize + localInner;
1122
1123 result.m_values(blockId * BlockSize + offset) = it.value();
1124 }
1125 }
1126
1127 return result;
1128}
1129
1130// -----------------------------------------------------------------------------
1131// operator* (block-sparse product)
1132// -----------------------------------------------------------------------------
1133
1134template <typename Scalar_, int Options_, int BlockRows_, int BlockCols_, typename StorageIndex_>
1135template <int RhsBlockCols>
1138 const BlockSparseMatrix<Scalar_, Options_, BlockCols_, RhsBlockCols, StorageIndex_>& rhs) const {
1139 using RhsMatrix = BlockSparseMatrix<Scalar_, Options_, BlockCols_, RhsBlockCols, StorageIndex_>;
1140 using ResultMatrix = BlockSparseMatrix<Scalar_, Options_, BlockRows_, RhsBlockCols, StorageIndex_>;
1142 constexpr int ResultBlockSize = BlockRows_ * RhsBlockCols;
1143
1144 eigen_assert(blockCols() == rhs.blockRows() && "BlockSparseMatrix product: lhs.blockCols() != rhs.blockRows()");
1145
1146 Index cBlockRows = blockRows();
1147 Index cBlockCols = rhs.blockCols();
1148 ResultMatrix result(cBlockRows, cBlockCols);
1149
1150 // For ColMajor: mask / accum indexed by block-row (size = cBlockRows).
1151 // For RowMajor: mask / accum indexed by block-col (size = cBlockCols).
1152 Index maskSize = IsRowMajor ? cBlockCols : cBlockRows;
1154 Array<Scalar_, Dynamic, 1> accumData(maskSize * ResultBlockSize);
1155 Array<Index, Dynamic, 1> indices(maskSize);
1156 Index nIndices = 0;
1157 // The mask is read and written through coeff/coeffRef below: the block indices
1158 // are in range by construction, and operator()'s bounds check gives GCC 14+ a
1159 // false -Wstringop-overflow on a negative StorageIndex_.
1160
1161 // Grow result storage geometrically rather than pre-allocating the dense
1162 // worst case (cBlockRows*cBlockCols blocks): the product is typically far
1163 // sparser than that, so the dense bound would blow up peak memory.
1164 // capacity is always kept <= maxResultNnz (the true upper bound), and since
1165 // any single outer emits at most maskSize blocks, the initial estimate of
1166 // maskSize guarantees the first outer fits before the first grow check.
1167 Index cOuterSize = result.m_blockOuterSize;
1168 Index maxResultNnz = cBlockRows * cBlockCols;
1169 Index capacity = numext::mini(maxResultNnz, numext::maxi(maskSize, nonZeroBlocks() + rhs.nonZeroBlocks()));
1170 result.resizeBlockStorage_(capacity);
1171 Index nnz = 0;
1172
1173 for (Index out = 0; out < cOuterSize; ++out) {
1174 result.m_outerIndex(out) = StorageIndex_(nnz);
1175
1176 if (!IsRowMajor) {
1177 // ColMajor: out is block-column j of the result.
1178 // For each block B(k,j) and each block A(bi,k): C(bi,j) += A(bi,k)*B(k,j).
1179 Index j = out;
1180 for (Index rhsId = rhs.m_outerIndex(j); rhsId < rhs.m_outerIndex(j + 1); ++rhsId) {
1181 Index k = rhs.m_innerIndex(rhsId);
1182 typename RhsMatrix::ConstBlockMap Bkj = rhs.blockRef(rhsId);
1183 for (Index lhsId = m_outerIndex(k); lhsId < m_outerIndex(k + 1); ++lhsId) {
1184 Index bi = m_innerIndex(lhsId);
1185 if (!mask.coeff(bi)) {
1186 mask.coeffRef(bi) = 1;
1187 Map<ResultBlock>(accumData.data() + bi * ResultBlockSize).noalias() = blockRef(lhsId) * Bkj;
1188 indices(nIndices++) = bi;
1189 } else {
1190 Map<ResultBlock>(accumData.data() + bi * ResultBlockSize).noalias() += blockRef(lhsId) * Bkj;
1191 }
1192 }
1193 }
1194 } else {
1195 // RowMajor: out is block-row bi of the result.
1196 // For each block A(bi,k) and each block B(k,j): C(bi,j) += A(bi,k)*B(k,j).
1197 Index bi = out;
1198 for (Index lhsId = m_outerIndex(bi); lhsId < m_outerIndex(bi + 1); ++lhsId) {
1199 Index k = m_innerIndex(lhsId);
1200 ConstBlockMap Aik = blockRef(lhsId);
1201 for (Index rhsId = rhs.m_outerIndex(k); rhsId < rhs.m_outerIndex(k + 1); ++rhsId) {
1202 Index j = rhs.m_innerIndex(rhsId);
1203 if (!mask.coeff(j)) {
1204 mask.coeffRef(j) = 1;
1205 Map<ResultBlock>(accumData.data() + j * ResultBlockSize).noalias() = Aik * rhs.blockRef(rhsId);
1206 indices(nIndices++) = j;
1207 } else {
1208 Map<ResultBlock>(accumData.data() + j * ResultBlockSize).noalias() += Aik * rhs.blockRef(rhsId);
1209 }
1210 }
1211 }
1212 }
1213
1214 // Sort the accumulated indices so the result's inner index array is sorted.
1215 std::sort(indices.data(), indices.data() + nIndices);
1216 if (nnz + nIndices > capacity) {
1217 capacity = numext::mini(maxResultNnz, numext::maxi(2 * capacity, nnz + nIndices));
1218 result.conservativeResizeBlockStorage_(capacity);
1219 }
1220 for (Index ki = 0; ki < nIndices; ++ki) {
1221 Index idx = indices(ki);
1222 result.m_innerIndex(nnz) = StorageIndex_(idx);
1223 result.blockRef(nnz) = Map<ResultBlock>(accumData.data() + idx * ResultBlockSize);
1224 mask.coeffRef(idx) = 0;
1225 ++nnz;
1226 }
1227 nIndices = 0;
1228 }
1229 result.m_outerIndex(cOuterSize) = StorageIndex_(nnz);
1230
1231 // Trim to actual number of result blocks.
1232 result.conservativeResizeBlockStorage_(nnz);
1233
1234 return result;
1235}
1236
1237// =============================================================================
1238// BlockSparseTriangularView
1239// =============================================================================
1240
1256template <typename BSM, int Mode, bool DiagIsTriangular = false>
1257class BlockSparseTriangularView {
1258 public:
1259 using Scalar = typename BSM::Scalar;
1260 using StorageIndex = typename BSM::StorageIndex;
1261 using BlockType = typename BSM::BlockType;
1262 using BlockMap = typename BSM::BlockMap;
1263 using ConstBlockMap = typename BSM::ConstBlockMap;
1264 static constexpr int BlockRows = BSM::BlockRows;
1265 static constexpr int BlockCols = BSM::BlockCols;
1266 static constexpr int BlockSize = BSM::BlockSize;
1267 static constexpr bool IsRowMajor = BSM::IsRowMajor;
1268 static constexpr bool IsUpper = (Mode & Upper) != 0;
1269
1270 explicit BlockSparseTriangularView(const BSM& m) : m_matrix(m) {}
1271
1272 Index rows() const { return m_matrix.rows(); }
1273 Index cols() const { return m_matrix.cols(); }
1274
1275 // ---- Materialize ---------------------------------------------------------
1276
1280 BSM eval() const {
1281 constexpr int ZeroMode = IsUpper ? StrictlyLower : StrictlyUpper;
1282 const BSM& m = m_matrix;
1283 BSM result(m.blockRows(), m.blockCols());
1284 result.resizeBlockStorage_(m.nonZeroBlocks());
1285 Index nnz = 0;
1286
1287 for (Index out = 0; out < m.m_blockOuterSize; ++out) {
1288 result.m_outerIndex(out) = StorageIndex(nnz);
1289 for (Index id = m.m_outerIndex(out); id < m.m_outerIndex(out + 1); ++id) {
1290 Index inner = m.m_innerIndex(id);
1291 Index bi = IsRowMajor ? out : inner;
1292 Index bj = IsRowMajor ? inner : out;
1293 if (IsUpper ? (bj < bi) : (bj > bi)) continue;
1294 result.m_innerIndex(nnz) = StorageIndex(inner);
1295 result.m_values.template segment<BlockSize>(nnz * BlockSize) =
1296 m.m_values.template segment<BlockSize>(id * BlockSize);
1297 EIGEN_IF_CONSTEXPR (!DiagIsTriangular) {
1298 if (bi == bj)
1299 BlockMap(result.m_values.data() + nnz * BlockSize).template triangularView<ZeroMode>().setZero();
1300 }
1301 ++nnz;
1302 }
1303 }
1304 result.m_outerIndex(m.m_blockOuterSize) = StorageIndex(nnz);
1305 result.conservativeResizeBlockStorage_(nnz);
1306 return result;
1307 }
1308
1311
1312 // ---- Arithmetic ----------------------------------------------------------
1313
1314 BSM operator+(const BlockSparseTriangularView& other) const { return eval() + other.eval(); }
1315 BSM operator-(const BlockSparseTriangularView& other) const { return eval() - other.eval(); }
1316
1318 template <int RhsBlockCols>
1323
1324 // ---- Dense products (no intermediate materialisation) --------------------
1325
1326 template <typename OtherDerived>
1328 EIGEN_STATIC_ASSERT(
1329 (std::is_same<Scalar, typename OtherDerived::Scalar>::value),
1330 YOU_MIXED_DIFFERENT_NUMERIC_TYPES__YOU_NEED_TO_USE_THE_CAST_METHOD_OF_MATRIXBASE_TO_CAST_NUMERIC_TYPES_EXPLICITLY)
1331 EIGEN_INTERNAL_ASSERT_PRODUCT_SHAPE_MSG(m_matrix, rhs, "BlockSparseTriangularView * Dense: dimension mismatch");
1333 ResultType result = ResultType::Zero(m_matrix.rows(), rhs.cols());
1334 for (Index out = 0; out < m_matrix.m_blockOuterSize; ++out) {
1335 for (Index id = m_matrix.m_outerIndex(out); id < m_matrix.m_outerIndex(out + 1); ++id) {
1336 Index inner = m_matrix.m_innerIndex(id);
1337 Index bi = IsRowMajor ? out : inner;
1338 Index bj = IsRowMajor ? inner : out;
1339 if (IsUpper ? (bj < bi) : (bj > bi)) continue;
1340 constexpr int DiagMode = IsUpper ? Upper : Lower;
1341 if (!DiagIsTriangular && bi == bj)
1342 result.template middleRows<BlockRows>(bi * BlockRows).noalias() +=
1343 m_matrix.blockRef(id).template triangularView<DiagMode>() *
1344 rhs.template middleRows<BlockCols>(bj * BlockCols);
1345 else
1346 result.template middleRows<BlockRows>(bi * BlockRows).noalias() +=
1347 m_matrix.blockRef(id) * rhs.template middleRows<BlockCols>(bj * BlockCols);
1348 }
1349 }
1350 return result;
1351 }
1352
1353 template <typename OtherDerived>
1354 friend Matrix<Scalar, OtherDerived::RowsAtCompileTime, Dynamic> operator*(const MatrixBase<OtherDerived>& lhs,
1355 const BlockSparseTriangularView& tri) {
1356 EIGEN_STATIC_ASSERT(
1357 (std::is_same<Scalar, typename OtherDerived::Scalar>::value),
1358 YOU_MIXED_DIFFERENT_NUMERIC_TYPES__YOU_NEED_TO_USE_THE_CAST_METHOD_OF_MATRIXBASE_TO_CAST_NUMERIC_TYPES_EXPLICITLY)
1359 EIGEN_INTERNAL_ASSERT_PRODUCT_SHAPE_MSG(lhs, tri.m_matrix, "Dense * BlockSparseTriangularView: dimension mismatch");
1360 constexpr bool isRM = BSM::IsRowMajor;
1361 using ResultType = Matrix<Scalar, OtherDerived::RowsAtCompileTime, Dynamic>;
1362 // BSM befriends BlockSparseTriangularView, but GCC <= 11 and MSVC do not
1363 // extend that friendship to the body of a friend function defined inside
1364 // the view (CWG 1699), so only BSM's public interface may be used here.
1365 const BSM& m = tri.m_matrix;
1366 const StorageIndex* outerPtr = m.outerIndexPtr();
1367 const StorageIndex* innerPtr = m.innerIndexPtr();
1368 ResultType result = ResultType::Zero(lhs.rows(), m.cols());
1369 for (Index out = 0; out < m.blockOuterSize(); ++out) {
1370 for (Index id = outerPtr[out]; id < outerPtr[out + 1]; ++id) {
1371 Index inner = innerPtr[id];
1372 Index bi = isRM ? out : inner;
1373 Index bj = isRM ? inner : out;
1374 if (IsUpper ? (bj < bi) : (bj > bi)) continue;
1375 constexpr int DiagMode = IsUpper ? Upper : Lower;
1376 if (!DiagIsTriangular && bi == bj)
1377 result.template middleCols<BlockCols>(bj * BlockCols).noalias() +=
1378 lhs.template middleCols<BlockRows>(bi * BlockRows) * m.blockRef(id).template triangularView<DiagMode>();
1379 else
1380 result.template middleCols<BlockCols>(bj * BlockCols).noalias() +=
1381 lhs.template middleCols<BlockRows>(bi * BlockRows) * m.blockRef(id);
1382 }
1383 }
1384 return result;
1385 }
1386
1387 // ---- Triangular solve -------------------------------------------------------
1388
1395 template <typename Derived>
1397 doSolveImpl<false, false>(x.derived());
1398 }
1399
1402 const BlockSparseTriangularView& m_tri;
1403 template <typename Derived>
1404 void solveInPlace(MatrixBase<Derived>& x) const {
1405 m_tri.template doSolveImpl<true, false>(x.derived());
1406 }
1407 };
1408
1411 const BlockSparseTriangularView& m_tri;
1412 template <typename Derived>
1413 void solveInPlace(MatrixBase<Derived>& x) const {
1414 m_tri.template doSolveImpl<true, true>(x.derived());
1415 }
1416 };
1417
1418 TransposeReturnType transpose() const { return {*this}; }
1419 AdjointReturnType adjoint() const { return {*this}; }
1420
1421 private:
1422 const BSM& m_matrix;
1423
1424 // Non-transposed solve for both storage orders.
1425 //
1426 // diagFirst = (IsUpper == IsRowMajor): ColMajor Lower→first, ColMajor Upper→last,
1427 // RowMajor Lower→last, RowMajor Upper→first.
1428 // Loop direction: forward for Lower, backward for Upper (same for both storage orders).
1429 // ColMajor: solve diagonal first, then scatter x[inner] -= blk * x[k].
1430 // RowMajor: gather x[k] -= blk * x[inner] first, then solve diagonal.
1431 template <typename Derived>
1432 void doSolveDirect(Derived& x) const {
1433 EIGEN_STATIC_ASSERT(BlockRows == BlockCols, THIS_METHOD_IS_ONLY_FOR_SQUARE_BLOCK_MATRICES)
1434 constexpr int DiagMode = IsUpper ? Upper : Lower;
1435 constexpr bool diagFirst = (IsUpper == BSM::IsRowMajor);
1436 Index nb = m_matrix.blockCols(); // == blockRows() for square matrices
1437 EIGEN_INTERNAL_ASSERT_SAME_ROWS_MSG(x, m_matrix, "solveInPlace: size mismatch");
1438
1439 const StorageIndex* innerPtr = m_matrix.innerIndexPtr();
1440 const StorageIndex* outerPtr = m_matrix.outerIndexPtr();
1441
1442 Index outerStart = IsUpper ? nb - 1 : 0;
1443 Index outerEnd = IsUpper ? -1 : nb;
1444 constexpr Index kStep = IsUpper ? -1 : 1;
1445
1446 for (Index k = outerStart; k != outerEnd; k += kStep) {
1447 const StorageIndex* beg = innerPtr + outerPtr[k];
1448 const StorageIndex* end = innerPtr + outerPtr[k + 1];
1449 // A general stored matrix also holds blocks of the opposite triangle; skip them.
1450 if (diagFirst) beg = std::lower_bound(beg, end, StorageIndex(k));
1451 if (!diagFirst) end = std::upper_bound(beg, end, StorageIndex(k));
1452 eigen_assert(beg != end && "solveInPlace: missing diagonal block");
1453 if (beg == end) continue;
1454 const StorageIndex* diag_ptr = diagFirst ? beg : end - 1;
1455 const StorageIndex* off_beg = diagFirst ? beg + 1 : beg;
1456 const StorageIndex* off_end = diagFirst ? end : end - 1;
1457 eigen_assert(*diag_ptr == k);
1458 EIGEN_IF_CONSTEXPR (!BSM::IsRowMajor) {
1459 m_matrix.blockRef(diag_ptr - innerPtr)
1460 .template triangularView<DiagMode>()
1461 .solveInPlace(x.template middleRows<BlockRows>(k * BlockRows));
1462 for (const StorageIndex* it = off_beg; it != off_end; ++it)
1463 x.template middleRows<BlockRows>(*it * BlockRows).noalias() -=
1464 m_matrix.blockRef(it - innerPtr) * x.template middleRows<BlockRows>(k * BlockRows);
1465 } else {
1466 for (const StorageIndex* it = off_beg; it != off_end; ++it)
1467 x.template middleRows<BlockRows>(k * BlockRows).noalias() -=
1468 m_matrix.blockRef(it - innerPtr) * x.template middleRows<BlockRows>(*it * BlockRows);
1469 m_matrix.blockRef(diag_ptr - innerPtr)
1470 .template triangularView<DiagMode>()
1471 .solveInPlace(x.template middleRows<BlockRows>(k * BlockRows));
1472 }
1473 }
1474 }
1475
1476 // Transposed/adjoint solve for both storage orders.
1477 //
1478 // Loop direction: forward for Upper, backward for Lower (same for both storage orders).
1479 // ColMajor: gather x[k] -= adj(blk) * x[inner] first, then solve adj(diagonal).
1480 // RowMajor: solve adj(diagonal) first, then scatter x[inner] -= adj(blk) * x[k].
1481 template <bool Conjugate, typename Derived>
1482 void doSolveTransposed(Derived& x) const {
1483 EIGEN_STATIC_ASSERT(BlockRows == BlockCols, THIS_METHOD_IS_ONLY_FOR_SQUARE_BLOCK_MATRICES)
1484 constexpr int DiagMode = IsUpper ? Upper : Lower;
1485 constexpr bool diagFirst = (IsUpper == BSM::IsRowMajor);
1486 Index nb = m_matrix.blockCols(); // == blockRows() for square matrices
1487 EIGEN_INTERNAL_ASSERT_SAME_ROWS_MSG(x, m_matrix, "solveInPlace: size mismatch");
1488
1489 const StorageIndex* innerPtr = m_matrix.innerIndexPtr();
1490 const StorageIndex* outerPtr = m_matrix.outerIndexPtr();
1491
1492 Index outerStart = IsUpper ? 0 : nb - 1;
1493 Index outerEnd = IsUpper ? nb : -1;
1494 constexpr Index kStep = IsUpper ? 1 : -1;
1495
1496 for (Index k = outerStart; k != outerEnd; k += kStep) {
1497 const StorageIndex* beg = innerPtr + outerPtr[k];
1498 const StorageIndex* end = innerPtr + outerPtr[k + 1];
1499 // A general stored matrix also holds blocks of the opposite triangle; skip them.
1500 if (diagFirst) beg = std::lower_bound(beg, end, StorageIndex(k));
1501 if (!diagFirst) end = std::upper_bound(beg, end, StorageIndex(k));
1502 eigen_assert(beg != end && "solveInPlace: missing diagonal block");
1503 if (beg == end) continue;
1504 const StorageIndex* diag_ptr = diagFirst ? beg : end - 1;
1505 const StorageIndex* off_beg = diagFirst ? beg + 1 : beg;
1506 const StorageIndex* off_end = diagFirst ? end : end - 1;
1507 eigen_assert(*diag_ptr == k);
1508 EIGEN_IF_CONSTEXPR (!BSM::IsRowMajor) {
1509 for (const StorageIndex* it = off_beg; it != off_end; ++it)
1510 x.template middleRows<BlockRows>(k * BlockRows).noalias() -=
1511 internal::adjoint_if<Conjugate>(m_matrix.blockRef(it - innerPtr)) *
1512 x.template middleRows<BlockRows>(*it * BlockRows);
1513 internal::adjoint_if<Conjugate>(m_matrix.blockRef(diag_ptr - innerPtr).template triangularView<DiagMode>())
1514 .solveInPlace(x.template middleRows<BlockRows>(k * BlockRows));
1515 } else {
1516 internal::adjoint_if<Conjugate>(m_matrix.blockRef(diag_ptr - innerPtr).template triangularView<DiagMode>())
1517 .solveInPlace(x.template middleRows<BlockRows>(k * BlockRows));
1518 for (const StorageIndex* it = off_beg; it != off_end; ++it)
1519 x.template middleRows<BlockRows>(*it * BlockRows).noalias() -=
1520 internal::adjoint_if<Conjugate>(m_matrix.blockRef(it - innerPtr)) *
1521 x.template middleRows<BlockRows>(k * BlockRows);
1522 }
1523 }
1524 }
1525
1526 template <bool Transposed, bool Conjugate, typename Derived>
1527 void doSolveImpl(Derived& x) const {
1528 EIGEN_IF_CONSTEXPR (!Transposed)
1529 doSolveDirect(x);
1530 else
1531 doSolveTransposed<Conjugate>(x);
1532 }
1533};
1534
1535// =============================================================================
1536// BlockSparseSelfAdjointView
1537// =============================================================================
1538
1552template <typename BSM, int UpLo, bool DiagIsSelfAdjoint>
1553class BlockSparseSelfAdjointView {
1554 public:
1555 using Scalar = typename BSM::Scalar;
1556 using StorageIndex = typename BSM::StorageIndex;
1557 using BlockType = typename BSM::BlockType;
1558 using BlockMap = typename BSM::BlockMap;
1559 using ConstBlockMap = typename BSM::ConstBlockMap;
1560 static constexpr int BlockRows = BSM::BlockRows; // == BlockCols
1561 static constexpr int BlockCols = BSM::BlockCols;
1562 static constexpr int BlockSize = BSM::BlockSize;
1563 static constexpr bool IsRowMajor = BSM::IsRowMajor;
1564 static constexpr bool IsUpper = (UpLo & Upper) != 0;
1565 // UpLo passed to Eigen's dense selfadjointView on diagonal blocks:
1566 static constexpr int DiagUpLo = IsUpper ? Upper : Lower;
1567
1568 explicit BlockSparseSelfAdjointView(const BSM& m) : m_matrix(m) {}
1569
1570 Index rows() const { return m_matrix.rows(); }
1571 Index cols() const { return m_matrix.cols(); }
1572
1573 // ---- Materialize ---------------------------------------------------------
1574
1579 BSM eval() const {
1580 const BSM& m = m_matrix;
1581
1582 Index nDiag = 0, nOff = 0;
1583 for (Index out = 0; out < m.m_blockOuterSize; ++out)
1584 for (Index id = m.m_outerIndex(out); id < m.m_outerIndex(out + 1); ++id) {
1585 Index inner = m.m_innerIndex(id);
1586 Index bi = IsRowMajor ? out : inner;
1587 Index bj = IsRowMajor ? inner : out;
1588 if (IsUpper ? (bj < bi) : (bj > bi)) continue;
1589 if (bi == bj)
1590 ++nDiag;
1591 else
1592 ++nOff;
1593 }
1594
1595 Index nTotal = nDiag + 2 * nOff;
1596
1597 Array<StorageIndex, Dynamic, 1> brows(nTotal), bcols(nTotal);
1598 Array<Scalar, Dynamic, 1> bvals(nTotal * BlockSize);
1599
1600 Index k = 0;
1601 for (Index out = 0; out < m.m_blockOuterSize; ++out)
1602 for (Index id = m.m_outerIndex(out); id < m.m_outerIndex(out + 1); ++id) {
1603 Index inner = m.m_innerIndex(id);
1604 Index bi = IsRowMajor ? out : inner;
1605 Index bj = IsRowMajor ? inner : out;
1606 if (IsUpper ? (bj < bi) : (bj > bi)) continue;
1607
1608 brows(k) = StorageIndex(bi);
1609 bcols(k) = StorageIndex(bj);
1610 if (!DiagIsSelfAdjoint && bi == bj)
1611 BlockMap(bvals.data() + k * BlockSize) = m.blockRef(id).template selfadjointView<DiagUpLo>();
1612 else
1613 BlockMap(bvals.data() + k * BlockSize) = m.blockRef(id);
1614 ++k;
1615
1616 if (bi != bj) {
1617 brows(k) = StorageIndex(bj);
1618 bcols(k) = StorageIndex(bi);
1619 BlockMap(bvals.data() + k * BlockSize) = m.blockRef(id).adjoint();
1620 ++k;
1621 }
1622 }
1623
1624 // Sort by (outer, inner) then build BSM directly (no duplicates by construction).
1625 Array<Index, Dynamic, 1> perm(nTotal);
1626 std::iota(perm.data(), perm.data() + nTotal, Index(0));
1627 std::sort(perm.data(), perm.data() + nTotal, [&](Index a, Index b) {
1628 StorageIndex ao = IsRowMajor ? brows(a) : bcols(a);
1629 StorageIndex bo = IsRowMajor ? brows(b) : bcols(b);
1630 if (ao != bo) return ao < bo;
1631 return (IsRowMajor ? bcols(a) : brows(a)) < (IsRowMajor ? bcols(b) : brows(b));
1632 });
1633
1634 BSM result(m.blockRows(), m.blockCols());
1635 result.resizeBlockStorage_(nTotal);
1636
1637 for (Index ki = 0; ki < nTotal; ++ki) {
1638 Index pi = perm(ki);
1639 StorageIndex outer = IsRowMajor ? brows(pi) : bcols(pi);
1640 StorageIndex inner = IsRowMajor ? bcols(pi) : brows(pi);
1641 result.m_outerIndex(outer + 1)++;
1642 result.m_innerIndex(ki) = inner;
1643 result.m_values.template segment<BlockSize>(ki * BlockSize) = bvals.template segment<BlockSize>(pi * BlockSize);
1644 }
1645 for (Index j = 0; j < result.m_blockOuterSize; ++j) result.m_outerIndex(j + 1) += result.m_outerIndex(j);
1646
1647 return result;
1648 }
1649
1652
1653 // ---- Arithmetic ----------------------------------------------------------
1654
1655 BSM operator+(const BlockSparseSelfAdjointView& other) const { return eval() + other.eval(); }
1656 BSM operator-(const BlockSparseSelfAdjointView& other) const { return eval() - other.eval(); }
1657
1659 template <int RhsBlockCols>
1664
1665 // ---- Dense products (no materialisation; exploits both triangles) ---------
1666
1678 template <typename OtherDerived>
1680 EIGEN_STATIC_ASSERT(
1681 (std::is_same<Scalar, typename OtherDerived::Scalar>::value),
1682 YOU_MIXED_DIFFERENT_NUMERIC_TYPES__YOU_NEED_TO_USE_THE_CAST_METHOD_OF_MATRIXBASE_TO_CAST_NUMERIC_TYPES_EXPLICITLY)
1683 EIGEN_INTERNAL_ASSERT_PRODUCT_SHAPE_MSG(m_matrix, rhs, "BlockSparseSelfAdjointView * Dense: dimension mismatch");
1685 ResultType result = ResultType::Zero(m_matrix.rows(), rhs.cols());
1686
1687 for (Index out = 0; out < m_matrix.m_blockOuterSize; ++out)
1688 for (Index id = m_matrix.m_outerIndex(out); id < m_matrix.m_outerIndex(out + 1); ++id) {
1689 Index inner = m_matrix.m_innerIndex(id);
1690 Index bi = IsRowMajor ? out : inner;
1691 Index bj = IsRowMajor ? inner : out;
1692 if (IsUpper ? (bj < bi) : (bj > bi)) continue;
1693
1694 if (bi == bj) {
1695 EIGEN_IF_CONSTEXPR (DiagIsSelfAdjoint) {
1696 result.template middleRows<BlockRows>(bi * BlockRows).noalias() +=
1697 m_matrix.blockRef(id) * rhs.template middleRows<BlockCols>(bj * BlockCols);
1698 } else {
1699 // Materialize the tiny diagonal block as a fixed-size Hermitian matrix, then use the
1700 // ordinary (coeff-based for a vector rhs) product. This avoids the runtime-sized,
1701 // EIGEN_DONT_INLINE selfadjoint_matrix_vector_product kernel, which is tuned for large
1702 // matrices and is pure overhead for a 2-4 row block.
1703 BlockType diag = m_matrix.blockRef(id).template selfadjointView<DiagUpLo>();
1704 result.template middleRows<BlockRows>(bi * BlockRows).noalias() +=
1705 diag * rhs.template middleRows<BlockCols>(bj * BlockCols);
1706 }
1707 } else {
1708 result.template middleRows<BlockRows>(bi * BlockRows).noalias() +=
1709 m_matrix.blockRef(id) * rhs.template middleRows<BlockCols>(bj * BlockCols);
1710 result.template middleRows<BlockRows>(bj * BlockRows).noalias() +=
1711 m_matrix.blockRef(id).adjoint() * rhs.template middleRows<BlockRows>(bi * BlockRows);
1712 }
1713 }
1714 return result;
1715 }
1716
1718 template <typename OtherDerived>
1720 const BlockSparseSelfAdjointView& view) {
1721 EIGEN_STATIC_ASSERT(
1722 (std::is_same<Scalar, typename OtherDerived::Scalar>::value),
1723 YOU_MIXED_DIFFERENT_NUMERIC_TYPES__YOU_NEED_TO_USE_THE_CAST_METHOD_OF_MATRIXBASE_TO_CAST_NUMERIC_TYPES_EXPLICITLY)
1724 return (view * lhs.adjoint()).adjoint();
1725 }
1726
1727 private:
1728 const BSM& m_matrix;
1729};
1730
1731// =============================================================================
1732// BlockSparseMatrix::transposeImpl / transpose / adjoint (out-of-line)
1733// =============================================================================
1734
1735template <typename Scalar_, int Options_, int BlockRows_, int BlockCols_, typename StorageIndex_>
1736template <bool Conjugate>
1737BlockSparseMatrix<Scalar_, Options_, BlockCols_, BlockRows_, StorageIndex_>
1738BlockSparseMatrix<Scalar_, Options_, BlockRows_, BlockCols_, StorageIndex_>::transposeImpl() const {
1739 using ResultType = BlockSparseMatrix<Scalar_, Options_, BlockCols_, BlockRows_, StorageIndex_>;
1740 ResultType result(blockCols(), blockRows());
1741
1742 // Count entries per new outer (= old inner).
1743 for (Index id = 0; id < nonZeroBlocks(); ++id) result.m_outerIndex(m_innerIndex(id) + 1)++;
1744
1745 // Prefix sum.
1746 for (Index j = 0; j < result.m_blockOuterSize; ++j) result.m_outerIndex(j + 1) += result.m_outerIndex(j);
1747
1748 Index nnz = nonZeroBlocks();
1749 result.resizeBlockStorage_(nnz);
1750
1751 // One insertion cursor per new outer; start at the prefix-sum boundary.
1752 // Because we iterate oldOuter in increasing order, for each newOuter = oldInner
1753 // the emitted newInner = oldOuter values are automatically sorted.
1754 Array<StorageIndex_, Dynamic, 1> pos = result.m_outerIndex.head(result.m_blockOuterSize);
1755
1756 for (Index oldOuter = 0; oldOuter < m_blockOuterSize; ++oldOuter) {
1757 for (Index id = m_outerIndex(oldOuter); id < m_outerIndex(oldOuter + 1); ++id) {
1758 Index newOuter = m_innerIndex(id);
1759 Index insertAt = pos(newOuter)++;
1760 result.m_innerIndex(insertAt) = StorageIndex_(oldOuter);
1761 result.blockRef(insertAt) = internal::adjoint_if<Conjugate>(blockRef(id));
1762 }
1763 }
1764 return result;
1765}
1766
1767template <typename Scalar_, int Options_, int BlockRows_, int BlockCols_, typename StorageIndex_>
1772
1773template <typename Scalar_, int Options_, int BlockRows_, int BlockCols_, typename StorageIndex_>
1778
1779namespace internal {
1780
1781// ---------------------------------------------------------------------------
1782// generic_product_impl: BlockSparse × Dense → Dense
1783// Provides evalTo / addTo / subTo / scaleAndAddTo via generic_product_impl_base.
1784// ---------------------------------------------------------------------------
1785template <typename Lhs, typename Rhs, int ProductType>
1786struct generic_product_impl<Lhs, Rhs, BlockSparseShape, DenseShape, ProductType>
1787 : generic_product_impl_base<Lhs, Rhs, generic_product_impl<Lhs, Rhs, BlockSparseShape, DenseShape, ProductType>> {
1788 using Scalar = typename Product<Lhs, Rhs>::Scalar;
1789
1790 template <typename Dst>
1791 static void scaleAndAddTo(Dst& dst, const Lhs& lhs, const Rhs& rhs, const Scalar& alpha) {
1792 constexpr bool IsRM = (Lhs::Options & RowMajorBit) != 0;
1793 constexpr int BR = Lhs::BlockRows;
1794 constexpr int BC = Lhs::BlockCols;
1795 const typename Lhs::StorageIndex* outerPtr = lhs.outerIndexPtr();
1796 const typename Lhs::StorageIndex* innerPtr = lhs.innerIndexPtr();
1797 // Branch on alpha before the loop: alpha==1 and alpha==-1 avoid creating a
1798 // CwiseUnaryOp<scalar_multiple, B×B_block>, which defeats SIMD for complex scalars.
1799 bool a1 = (alpha == Scalar(1));
1800 bool am1 = (alpha == Scalar(-1));
1801 for (Eigen::Index out = 0; out < lhs.blockOuterSize(); ++out) {
1802 for (Eigen::Index id = outerPtr[out]; id < outerPtr[out + 1]; ++id) {
1803 Eigen::Index inner = innerPtr[id];
1804 Eigen::Index bi = IsRM ? out : inner;
1805 Eigen::Index bj = IsRM ? inner : out;
1806 auto dst_seg = dst.template middleRows<BR>(bi * BR);
1807 auto rhs_seg = rhs.template middleRows<BC>(bj * BC);
1808 if (EIGEN_PREDICT_TRUE(a1))
1809 dst_seg.noalias() += lhs.blockRef(id) * rhs_seg;
1810 else if (am1)
1811 dst_seg.noalias() -= lhs.blockRef(id) * rhs_seg;
1812 else {
1813 // Materialize block×rhs_seg into a small fixed-size stack buffer, then
1814 // scale by alpha. Keeps the B×B block as a plain Map for vectorization.
1816 TmpType tmp(BR, rhs.cols());
1817 tmp.noalias() = lhs.blockRef(id) * rhs_seg;
1818 dst_seg += alpha * tmp;
1819 }
1820 }
1821 }
1822 }
1823};
1824
1825// ---------------------------------------------------------------------------
1826// generic_product_impl: Dense × BlockSparse → Dense
1827// ---------------------------------------------------------------------------
1828template <typename Lhs, typename Rhs, int ProductType>
1829struct generic_product_impl<Lhs, Rhs, DenseShape, BlockSparseShape, ProductType>
1830 : generic_product_impl_base<Lhs, Rhs, generic_product_impl<Lhs, Rhs, DenseShape, BlockSparseShape, ProductType>> {
1831 using Scalar = typename Product<Lhs, Rhs>::Scalar;
1832
1833 template <typename Dst>
1834 static void scaleAndAddTo(Dst& dst, const Lhs& lhs, const Rhs& rhs, const Scalar& alpha) {
1835 constexpr bool IsRM = (Rhs::Options & RowMajorBit) != 0;
1836 constexpr int BR = Rhs::BlockRows;
1837 constexpr int BC = Rhs::BlockCols;
1838 const typename Rhs::StorageIndex* outerPtr = rhs.outerIndexPtr();
1839 const typename Rhs::StorageIndex* innerPtr = rhs.innerIndexPtr();
1840 bool a1 = (alpha == Scalar(1));
1841 bool am1 = (alpha == Scalar(-1));
1842 for (Eigen::Index out = 0; out < rhs.blockOuterSize(); ++out) {
1843 for (Eigen::Index id = outerPtr[out]; id < outerPtr[out + 1]; ++id) {
1844 Eigen::Index inner = innerPtr[id];
1845 Eigen::Index bi = IsRM ? out : inner;
1846 Eigen::Index bj = IsRM ? inner : out;
1847 auto dst_seg = dst.template middleCols<BC>(bj * BC);
1848 auto lhs_seg = lhs.template middleCols<BR>(bi * BR);
1849 if (EIGEN_PREDICT_TRUE(a1))
1850 dst_seg.noalias() += lhs_seg * rhs.blockRef(id);
1851 else if (am1)
1852 dst_seg.noalias() -= lhs_seg * rhs.blockRef(id);
1853 else {
1854 using TmpType = Matrix<Scalar, Lhs::RowsAtCompileTime, BC>;
1855 TmpType tmp(lhs.rows(), BC);
1856 tmp.noalias() = lhs_seg * rhs.blockRef(id);
1857 dst_seg += alpha * tmp;
1858 }
1859 }
1860 }
1861 }
1862};
1863
1864} // namespace internal
1865
1866} // end namespace Eigen
1867
1868#endif // EIGEN_BLOCKSPARSEMATRIX_H
General-purpose arrays with easy API for coefficient-wise operations.
Definition Array.h:55
constexpr const Scalar & coeff(Index rowId, Index colId) const
Definition PlainObjectBase.h:187
constexpr Scalar & coeffRef(Index rowId, Index colId)
Definition PlainObjectBase.h:205
Index blockCol() const
Definition BlockSparseMatrix.h:287
Index index() const
Definition BlockSparseMatrix.h:283
BlockMap valueRef()
Definition BlockSparseMatrix.h:292
ConstBlockMap value() const
Definition BlockSparseMatrix.h:290
Index outer() const
Definition BlockSparseMatrix.h:281
Index blockRow() const
Definition BlockSparseMatrix.h:285
A sparse matrix whose stored nonzeros are fixed-size dense blocks.
Definition BlockSparseMatrix.h:160
Index nonZeros() const
Definition BlockSparseMatrix.h:237
Index cols() const noexcept
Definition BlockSparseMatrix.h:217
BlockSparseMatrix operator+(const BlockSparseMatrix &other) const
Definition BlockSparseMatrix.h:476
Matrix< Scalar, Dynamic, 1 > diagonal() const
Definition BlockSparseMatrix.h:435
void reserve(Index n)
Definition BlockSparseMatrix.h:324
void setZero()
Definition BlockSparseMatrix.h:317
Index nonZeroBlocks() const
Definition BlockSparseMatrix.h:235
Scalar coeff(Index row, Index col) const
Definition BlockSparseMatrix.h:415
BlockSparseMatrix(Index blockRows, Index blockCols)
Definition BlockSparseMatrix.h:207
Index blockRows() const
Definition BlockSparseMatrix.h:220
Index rows() const noexcept
Definition BlockSparseMatrix.h:215
BlockSparseMatrix cwiseProduct(const BlockSparseMatrix &other) const
Definition BlockSparseMatrix.h:482
void resize(Index blockRows, Index blockCols)
Definition BlockSparseMatrix.h:309
friend BlockSparseMatrix operator*(const Scalar &s, const BlockSparseMatrix &m)
Definition BlockSparseMatrix.h:538
Index allocatedBlocks() const
Definition BlockSparseMatrix.h:239
void setFromOuterInner(Index blockRows, Index blockCols, Index nnzBlocks, const StorageIndex_ *outerPtr, const StorageIndex_ *innerPtr)
Definition BlockSparseMatrix.h:357
Index innerSize() const
Definition BlockSparseMatrix.h:232
Index blockCols() const
Definition BlockSparseMatrix.h:222
BlockSparseMatrix disjunctionExpr(const BlockSparseMatrix &other, ScalarFunc func) const
Definition BlockSparseMatrix.h:502
BlockSparseMatrix< Scalar_, Options_, BlockCols_, BlockRows_, StorageIndex_ > transpose() const
Definition BlockSparseMatrix.h:1769
BlockSparseMatrix conjunctionExpr(const BlockSparseMatrix &other, ScalarFunc func) const
Definition BlockSparseMatrix.h:509
void setFromTriplets(InputIterator begin, InputIterator end)
Definition BlockSparseMatrix.h:929
static BlockSparseMatrix fromSparse(const SparseMatrix< Scalar_, Options_, StorageIndex_ > &sp)
Definition BlockSparseMatrix.h:1060
BlockMap blockRef(Index k)
Definition BlockSparseMatrix.h:258
friend Product< OtherDerived, BlockSparseMatrix, AliasFreeProduct > operator*(const MatrixBase< OtherDerived > &lhs, const BlockSparseMatrix &bsm)
Definition BlockSparseMatrix.h:575
Index blockOuterSize() const
Definition BlockSparseMatrix.h:225
void squeeze()
Definition BlockSparseMatrix.h:329
BlockSparseMatrix operator-(const BlockSparseMatrix &other) const
Definition BlockSparseMatrix.h:479
BlockSparseTriangularView< BlockSparseMatrix, Mode, DiagIsTriangular > triangularView() const
Definition BlockSparseMatrix.h:646
void setIdentity()
Definition BlockSparseMatrix.h:339
BlockSparseSelfAdjointView< BlockSparseMatrix, UpLo, DiagIsSelfAdjoint > selfadjointView() const
Definition BlockSparseMatrix.h:667
Index outerSize() const
Definition BlockSparseMatrix.h:230
BlockSparseMatrix operator-() const
Definition BlockSparseMatrix.h:514
BlockSparseMatrix operator*(const Scalar &s) const
Definition BlockSparseMatrix.h:522
Index blockInnerSize() const
Definition BlockSparseMatrix.h:227
BlockSparseMatrix< Scalar_, Options_, BlockCols_, BlockRows_, StorageIndex_ > adjoint() const
Definition BlockSparseMatrix.h:1775
BlockSparseMatrix unaryExpr(ScalarFunc func) const
Definition BlockSparseMatrix.h:488
Product< BlockSparseMatrix, OtherDerived, AliasFreeProduct > operator*(const MatrixBase< OtherDerived > &rhs) const
Definition BlockSparseMatrix.h:557
ConstBlockMap blockRef(Index k) const
Definition BlockSparseMatrix.h:256
SparseMatrix< Scalar, Options_, StorageIndex_ > toSparse() const
Definition BlockSparseMatrix.h:1012
Lazy block-level self-adjoint (Hermitian) view of a BlockSparseMatrix.
Definition BlockSparseMatrix.h:1553
BSM eval() const
Definition BlockSparseMatrix.h:1579
friend Matrix< Scalar, OtherDerived::RowsAtCompileTime, Dynamic > operator*(const MatrixBase< OtherDerived > &lhs, const BlockSparseSelfAdjointView &view)
Definition BlockSparseMatrix.h:1719
SparseMatrix< Scalar, BSM::Options, StorageIndex > toSparse() const
Definition BlockSparseMatrix.h:1651
Matrix< Scalar, Dynamic, OtherDerived::ColsAtCompileTime > operator*(const MatrixBase< OtherDerived > &rhs) const
Definition BlockSparseMatrix.h:1679
BlockSparseMatrix< Scalar, BSM::Options, BlockRows, RhsBlockCols, StorageIndex > operator*(const BlockSparseMatrix< Scalar, BSM::Options, BlockCols, RhsBlockCols, StorageIndex > &rhs) const
Definition BlockSparseMatrix.h:1660
Lazy block-level triangular view of a BlockSparseMatrix.
Definition BlockSparseMatrix.h:1257
BlockSparseMatrix< Scalar, BSM::Options, BlockRows, RhsBlockCols, StorageIndex > operator*(const BlockSparseMatrix< Scalar, BSM::Options, BlockCols, RhsBlockCols, StorageIndex > &rhs) const
Definition BlockSparseMatrix.h:1319
SparseMatrix< Scalar, BSM::Options, StorageIndex > toSparse() const
Definition BlockSparseMatrix.h:1310
void solveInPlace(MatrixBase< Derived > &x) const
Definition BlockSparseMatrix.h:1396
BSM eval() const
Definition BlockSparseMatrix.h:1280
A (blockRow, blockCol, blockValue) triplet for assembling a BlockSparseMatrix.
Definition BlockSparseMatrix.h:89
A matrix or vector expression mapping an existing array of data.
Definition Map.h:97
Base class for all dense matrices, vectors, and expressions.
Definition MatrixBase.h:53
The matrix class, also used for vectors and row-vectors.
Definition Matrix.h:188
constexpr const Scalar * data() const
Definition PlainObjectBase.h:261
Derived & setZero(Index size)
Definition CwiseNullaryOp.h:536
Expression of the product of two arbitrary matrices or vectors.
Definition Product.h:211
A versatile sparse matrix representation.
Definition SparseMatrix.h:121
bool isCompressed() const
Definition SparseCompressedBase.h:115
Index cols() const
Definition SparseMatrix.h:162
Index rows() const
Definition SparseMatrix.h:160
void reserve(Index reserveSize)
Definition SparseMatrix.h:317
@ StrictlyLower
Definition Constants.h:224
@ StrictlyUpper
Definition Constants.h:226
@ Lower
Definition Constants.h:212
@ Upper
Definition Constants.h:214
constexpr unsigned int LvalueBit
Definition Constants.h:149
constexpr unsigned int RowMajorBit
Definition Constants.h:71
Definition BlockSparseMatrix.h:34
Definition BlockSparseMatrix.h:1410
Definition BlockSparseMatrix.h:31
Definition EigenBase.h:34