-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathmatrices.hpp
More file actions
4452 lines (4032 loc) · 151 KB
/
matrices.hpp
File metadata and controls
4452 lines (4032 loc) · 151 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
/**
* @file matrices.hpp
* @brief Matrix arithmetic library
* @author Christian Senger <senger@inue.uni-stuttgart.de>
* @version 2.2.3
* @date 2026
*
* @copyright
* Copyright (c) 2026, Christian Senger <senger@inue.uni-stuttgart.de>
*
* Licensed for noncommercial use only, including academic teaching, research, and personal non-profit purposes.
* Commercial use is prohibited without a separate commercial license. See the [LICENSE](../../LICENSE) file in the
* repository root for full terms and how to request a commercial license.
*
* @section Description
*
* This header file provides a complete implementation of matrix arithmetic and many linear algebra
* operations. It supports:
*
* - **details::Generic matrix operations**: Over any @ref CECCO::ComponentType including finite fields,
* floating-point numbers, complex numbers, and signed integers
* - **Specialized matrix types**: details::Zero, details::Identity, details::Diagonal, details::Vandermonde, and
* details::Toeplitz matrices with optimized operations
* - **Optimized linear algebra operations**: REF/RREF with binary field optimizations, cached rank computation,
* determinant, nullspace, characteristic polynomial, eigenvalue computation, and matrix inversion
* - **Cross-field operations**: Safe conversions between matrices over related fields using
* @ref CECCO::SubfieldOf, @ref CECCO::ExtensionOf, and @ref CECCO::largest_common_subfield_t
* - **Vector integration**: Bidirectional conversion Matrix -> Vector -> Matrix
* - **Performance optimizations**: STL algorithms, move semantics, and type-specific optimizations
*
* @section Usage_Examples
*
* @code{.cpp}
* Matrix<int> U = {{1, 2, 3}, {4, 5, 6}}; // 2x3 matrix
* Matrix<int> V(2, 3, 7); // 2x3 matrix filled with 7s
* auto W = U + V; // Element-wise addition
* auto X = U * V.transpose(); // Matrix multiplication
*
* // Special matrices (factories, results are type Matrix)
* auto I = IdentityMatrix<double>(3); // 3x3 identity matrix
* auto Z = ZeroMatrix<double>(2, 4); // 2x4 zero matrix
* Vector<double> v = {1, 2, 3};
* auto D = DiagonalMatrix(v); // 3x3 diagonal matrix
*
* // Finite field matrices
* Matrix<Fp<7>> P = {{1, 2}, {3, 4}};
* auto det = P.determinant(); // Determinant
* size_t rank = P.rank(); // Cached rank computation
* P.rref(); // Bring into RREF
*
* using F2 = Fp<2>;
* using F4 = Ext<F2, {1, 1, 1}>;
* Matrix<F4> Q = {{0, 1}, {2, 3}};
* auto nullspace = Q.basis_of_nullspace(); // Nullspace basis
* auto char_poly = Q.characteristic_polynomial(); // Characteristic polynomial
*
* // Cross-field operations (field tower compatibility)
* Vector<F4> r(10);
* r.randomize();
* auto R = r.as_matrix<F2>(); // Convert vector over superfield to matrix over subfield
* Matrix<F4> S(R); // Safe upcast: F₂ ⊆ F₄
* @endcode
*
* @section Matrix_Types
*
* The library supports several types of matrices:
* - **Generic**: General dense matrices with arbitrary elements
* - **Zero**: Matrices with all zero elements
* - **Identity**: Identity matrices
* - **Diagonal**: Diagonal matrices
* - **Vandermonde**: Vandermonde matrices
* - **Toeplitz**: Toeplitz matrices
*
* @note There is only one class template Matrix<T>! The type of matrix is only for internal use and transparent to the
* user of Matrix<T>. Example: Both IdentityMatrix<double>(3) and ZeroMatrix<double>(2, 4) return an instance
* of class (template) Matrix<T>!
*
* @section Performance_Features
*
* - **Optimized algorithms**: REF (Row Echelon Form) for efficient rank computation, binary field optimizations using
* constexpr if
* - **High-performance caching**: Rank computation uses caching
* - **Move semantics**: Optimal performance for temporary matrix operations
* - **STL integration**: Uses standard algorithms for optimal compiler optimization
* - **Type safety**: C++20 concepts prevent invalid operations:
* - @ref CECCO::ComponentType Ensures valid component types
* - @ref CECCO::largest_common_subfield_t Enables generalized cross-field conversions
*
* @see @ref fields.hpp for fields and field arithmetic
* @see @ref vectors.hpp for vectors and associated operations
* @see @ref field_concepts_traits.hpp for type constraints and field relationships (C++20 concepts)
*/
#ifndef MATRICES_HPP
#define MATRICES_HPP
#include <algorithm>
#include <cassert>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <ranges>
#include <set>
#include <sstream>
#include <unordered_map>
// #include <string> // transitive through field_concepts_traits.hpp
// #include <vector> // transitive through helpers.hpp
#include "field_concepts_traits.hpp"
// #include "helpers.hpp" // transitive through field_concepts_traits.hpp
// #include "InfInt.hpp" // transitive through field_concepts_traits.hpp
namespace CECCO {
namespace details {
/**
* @brief Enumeration of matrix types for operations (internal use only)
*
* This enum enables type-specific optimizations by tracking the structural properties
* of matrices. Different matrix types allow for specialized algorithms that can
* dramatically improve performance.
*
* @note Matrix type information is automatically maintained during operations.
* Operations that break the structure will demote to details::Generic type.
*/
enum matrix_type_t : uint8_t {
/**
* @brief Generic matrix with arbitrary elements
*/
Generic,
/**
* @brief Zero matrix with all elements equal to zero
*/
Zero,
/**
* @brief Diagonal matrix (square) with non-zero elements only on the main diagonal
*/
Diagonal,
/**
* @brief Identity matrix with ones on diagonal and zeros elsewhere
*/
Identity,
/**
* @brief Vandermonde matrix with arithmetic progressions (of pairwise distinct elements) in columns
*/
Vandermonde,
/**
* @brief Toeplitz matrix T_{i,j} = t_{i-j} with constant diagonals
*/
Toeplitz
};
} // namespace details
template <ComponentType T>
class Vector;
template <ComponentType T>
class Polynomial;
template <ComponentType T>
class Matrix;
template <ComponentType T>
constexpr Matrix<T> ZeroMatrix(size_t m, size_t n);
template <ComponentType T>
constexpr Matrix<T> IdentityMatrix(size_t m);
template <ComponentType T>
constexpr Matrix<T> DiagonalMatrix(const Vector<T>& v);
template <ComponentType T>
constexpr Matrix<T> ToeplitzMatrix(const Vector<T>& v, size_t m, size_t n);
template <ComponentType T>
constexpr Matrix<T> VandermondeMatrix(const Vector<T>& v, size_t m);
template <ComponentType T>
std::ostream& operator<<(std::ostream& os, const Matrix<T>& rhs) noexcept;
/**
* @class Matrix
* @brief Generic matrix class for error control coding (CECCO) and finite field applications
*
* @tparam T Component type satisfying @ref CECCO::ComponentType concept. Supported types include:
* - **Finite field types**: @ref CECCO::Fp, @ref CECCO::Ext satisfying @ref CECCO::FiniteFieldType
* - **Floating-point type**: `double`
* - **Complex type**: `std::complex<double>`
* - **Signed integer types**: Signed integer types including `InfInt` satisfying @ref CECCO::SignedIntType
*
* The Matrix class provides a linear algebra framework for error control
* coding applications. It supports both dense and structured matrix types with automatic
* optimization based on matrix structure.
*
* @section Implementation_Notes
*
* - **Cross-field compatibility**: Safe conversions between related field types using concepts
* - **CECCO-specific operations**: Hamming weight, Hamming distance, burst length calculations
* - **Type safety**: Compile-time validation of field relationships and operations
*
* - **Automatic type optimization**: Recognizes and optimizes for special matrix structures
* (Zero, Identity, Diagonal, Vandermonde, Toeplitz) with significant
* performance gains
* - **Cross-field compatibility**: Safe conversions between matrices over related fields
* using C++20 concepts for field tower relationships
* - **Optimized linear algebra**: REF/RREF with binary field optimizations, cached rank computation,
* determinant, nullspace, eigenvalues, matrix inversion, characteristic polynomial computation
*
* @section Matrix_Types
*
* The library supports several types of matrices:
* - **Generic**: General dense matrices with arbitrary elements
* - **Zero**: Matrices with all zero elements
* - **Identity**: Identity matrices
* - **Diagonal**: Diagonal matrices
* - **Vandermonde**: Vandermonde matrices
* - **Toeplitz**: Toeplitz matrices
*
* @section Usage_Examples
*
* @code{.cpp}
* Matrix<int> U = {{1, 2, 3}, {4, 5, 6}}; // 2x3 matrix
* Matrix<int> V(2, 3, 7); // 2x3 matrix filled with 7s
* auto W = U + V; // Element-wise addition
* auto X = U * V.transpose(); // Matrix multiplication
*
* // Special matrices (factories, results are type Matrix)
* auto I = IdentityMatrix<double>(3); // 3x3 identity matrix
* auto Z = ZeroMatrix<double>(2, 4); // 2x4 zero matrix
* Vector<double> v = {1, 2, 3};
* auto D = DiagonalMatrix(v); // 3x3 diagonal matrix
*
* // Finite field matrices
* Matrix<Fp<7>> P = {{1, 2}, {3, 4}};
* auto det = P.determinant(); // Determinant
* size_t rank = P.rank(); // Cached rank computation
* P.rref(); // Bring into RREF
*
* using F2 = Fp<2>;
* using F4 = Ext<F2, {1, 1, 1}>;
* Matrix<F4> Q = {{0, 1}, {2, 3}};
* auto nullspace = Q.basis_of_nullspace(); // Nullspace basis
* auto char_poly = Q.characteristic_polynomial(); // Characteristic polynomial
*
* // Cross-field operations (field tower compatibility)
* Vector<F4> r(10);
* r.randomize();
* auto R = r.as_matrix<F2>(); // Convert vector over superfield to matrix over subfield
* Matrix<F4> S(R); // Safe upcast: F₂ ⊆ F₄
* @endcode
*
* @section Template Constraints
*
* - **Basic operations**: Available for all @ref CECCO::ComponentType
* - **Field operations**: RREF, inversion, nullspace require @ref CECCO::FieldType
* - **Cross-field operations**: Require same characteristic using @ref CECCO::largest_common_subfield_t
* - **Finite field specific**: Some operations require @ref CECCO::FiniteFieldType
*
* @warning Matrix operations assume compatible dimensions. Operations on incompatible
* matrices throw `std::invalid_argument` exceptions.
*
* @note The class maintains strong exception safety guarantees. Failed operations
* leave the matrix in its original state.
*
* @see @ref CECCO::Vector for vector operations and matrix-vector conversions
* @see @ref CECCO::details::matrix_type_t for matrix type optimizations
* @see @ref CECCO::ComponentType for supported component types
* @see @ref CECCO::FieldType, @ref CECCO::FiniteFieldType for field operation constraints
* @see @ref CECCO::largest_common_subfield_t for cross-field operation requirements
*/
template <ComponentType T>
class Matrix {
friend constexpr Matrix<T> IdentityMatrix<>(size_t m);
friend constexpr Matrix<T> DiagonalMatrix<>(const Vector<T>& v);
friend constexpr Matrix<T> ToeplitzMatrix<>(const Vector<T>& v, size_t m, size_t n);
friend constexpr Matrix<T> VandermondeMatrix<>(const Vector<T>& v, size_t m);
template <ReliablyComparableType U>
friend constexpr bool operator==(const Matrix<U>& lhs, const Matrix<U>& rhs) noexcept;
friend std::ostream& operator<< <>(std::ostream& os, const Matrix& rhs) noexcept;
template <ComponentType>
friend class Matrix;
public:
/**
* @brief Default constructor creating an empty matrix
*
* Creates a matrix with zero dimensions (0 × 0). The matrix is considered empty
* and has @ref details::Zero type by default.
*/
constexpr Matrix() noexcept : data(0) {}
/**
* @brief Constructs a zero matrix of specified dimensions
*
* @param m Number of rows
* @param n Number of columns
*
* Creates an m × n zero matrix with all elements initialized to T(0).
* Automatically sets matrix type to @ref details::Zero for optimization.
*
* @throws std::bad_alloc if memory allocation fails
*/
constexpr Matrix(size_t m, size_t n) : data(m * n), m(m), n(n), type(details::Zero) {}
/**
* @brief Constructs a matrix filled with a specific value from T
*
* @param m Number of rows
* @param n Number of columns
* @param l Value to assign to all elements
*
* Creates an m × n matrix with all elements set to the specified value.
* Matrix type is automatically set to @ref details::Zero if value is T(0), otherwise @ref details::Generic.
*
* @throws std::bad_alloc if memory allocation fails
*/
Matrix(size_t m, size_t n, const T& l);
/**
* @brief Constructs a matrix from a flat initializer list
*
* @param m Number of rows
* @param n Number of columns
* @param l Initializer list containing m*n elements from T in row-major order
*
* Creates an m × n matrix from elements provided in row-major order.
*
* @throws std::invalid_argument if initializer list size doesn't match m*n
* @throws std::bad_alloc if memory allocation fails
*
* @code{.cpp}
* Matrix<int> M(2, 3, {1, 2, 3, 4, 5, 6}); // 2 × 3 matrix
* @endcode
*/
constexpr Matrix(size_t m, size_t n, std::initializer_list<T> l);
/**
* @brief Constructs a matrix from nested initializer lists
*
* @param l Nested initializer list where each inner list represents a row
*
* Creates a matrix from a 2D initializer list structure. Dimensions are
* automatically determined from the initializer list structure.
*
* @throws std::bad_alloc if memory allocation fails
*
* @code{.cpp}
* Matrix<int> M = {{1, 2, 3}, {4, 5, 6}}; // 2 × 3 matrix
* @endcode
*
* @note Rows with different lengths are zero-padded to match the longest row
*/
Matrix(std::initializer_list<std::initializer_list<T>> l);
/**
* @brief Constructs a single-row matrix from a vector
*
* @param v Vector to convert into a 1 × n matrix
*
* Creates a 1 × n matrix (row vector) from the provided vector.
* Matrix type is set to @ref details::Toeplitz for optimization.
*
* @throws std::bad_alloc if memory allocation fails
*
* @code{.cpp}
* Vector<int> v = {1, 2, 3, 4};
* Matrix<int> M(v); // 1 × 4 matrix
* @endcode
*/
Matrix(const Vector<T>& v);
/**
* @brief Copy constructor
*
* @param other Matrix to copy from
*
* @throws std::bad_alloc if memory allocation fails
*/
constexpr Matrix(const Matrix& other)
: data(other.data),
m(other.m),
n(other.n),
transposed(other.transposed),
type(other.type),
cache(other.cache) {}
/**
* @brief Move constructor
*
* @param other Matrix to move from (left in valid but unspecified state)
*/
constexpr Matrix(Matrix&& other) noexcept
: data(std::move(other.data)),
m(other.m),
n(other.n),
transposed(other.transposed),
type(other.type),
cache(std::move(other.cache)) {}
/**
* @brief Cross-field copy constructor for finite fields with the same characteristic
*
* @tparam S Source finite field type that must have the same characteristic as T
* @param other Matrix over finite field S to copy from
*
* Safely converts matrices between any finite fields with the same characteristic using
* @ref largest_common_subfield_t as the conversion bridge. Supports conversions across
* different field towers, not just within the same construction hierarchy.
*
* @throws std::invalid_argument if field components cannot be represented in target field (downcasting not
* possible)
* @throws std::bad_alloc if memory allocation fails
*
* @note Available for any finite field types with matching characteristics
*/
template <FiniteFieldType S>
constexpr Matrix(const Matrix<S>& other)
requires FiniteFieldType<T> && (T::get_characteristic() == S::get_characteristic());
/**
* @brief Construct matrix from a PPM (P3) image file
*
* @param filename Path to the input PPM file (ASCII P3 format)
*
* Reads a PPM image and constructs an m × n matrix (m = height, n = width)
* by mapping each pixel's RGB triplet back to a field element label using the
* same 64-entry colormap as @ref export_as_ppm. Pixels whose RGB values do not
* match any colormap entry are treated as erased (when @c CECCO_ERASURE_SUPPORT
* is defined) or set to a random field element.
*
* @note Only available for finite field types with field size at most 64
* @note The input file must use the colormap palette. To convert any image
* (PNG, JPG, etc.) into the appropriate PPM format, use ImageMagick:
* @code{.sh}
* magick input.png -alpha remove -background black +dither -remap palette.ppm -compress none output.ppm
* @endcode
*
* @code{.cpp}
* using F4 = Ext<Fp<2>, MOD{1, 1, 1}>;
* Matrix<F4> M("matrix.ppm");
* @endcode
*/
Matrix(const std::string& filename)
requires FiniteFieldType<T> && (T::get_size() <= 64);
/** @name Assignment Operators
* @{
*/
/**
* @brief Copy assignment operator
*
* @param rhs Matrix to copy from
* @return Reference to this matrix after assignment
*
* @throws std::bad_alloc if memory allocation fails
*/
constexpr Matrix& operator=(const Matrix& rhs);
/**
* @brief Move assignment operator
*
* @param rhs Matrix to move from (left in valid but unspecified state)
* @return Reference to this matrix after assignment
*/
constexpr Matrix& operator=(Matrix&& rhs) noexcept;
/**
* @brief Cross-field assignment operator between fields with the same characteristic
*
* @tparam S Source field type that must have the same characteristic as T
* @param rhs Matrix over field S to convert
* @return Reference to this matrix after assignment
*
* Safely converts matrices between any fields with the same characteristic using
* @ref largest_common_subfield_t as the conversion bridge. Supports conversions across
* different field towers, not just within the same construction hierarchy.
*
* @throws std::invalid_argument if field components cannot be represented in target field (downcasting not
* possible)
* @throws std::bad_alloc if memory allocation fails
*
* @note Available for any field types with matching characteristics
*/
template <FieldType S>
constexpr Matrix& operator=(const Matrix<S>& other)
requires FiniteFieldType<S> && FiniteFieldType<T> && (S::get_characteristic() == T::get_characteristic());
/** @} */
/** @name Unary Arithmetic Operations
* @{
*/
/**
* @brief Unary plus operator for lvalue references (identity)
*
* @return Copy of this matrix (mathematical identity operation)
*/
constexpr Matrix operator+() const& noexcept { return *this; }
/**
* @brief Unary plus operator for rvalue references (move optimization)
*
* @return This matrix moved (mathematical identity operation)
*/
constexpr Matrix operator+() && noexcept { return std::move(*this); }
/**
* @brief Unary minus operator for lvalue references
*
* @return New matrix with all elements negated
*/
constexpr Matrix operator-() const& noexcept;
/**
* @brief Unary minus operator for rvalue references (move optimization)
*
* @return This matrix with all elements negated in-place
*
* @note This modifies the matrix in-place (move operation)
*/
constexpr Matrix operator-() && noexcept;
/** @} */
/** @name Compound Assignment Operations
* @{
*/
/**
* @brief Matrix addition assignment
*
* @param rhs Matrix to add to this matrix
* @return Reference to this matrix after addition
*
* Performs element-wise addition: this[i,j] += rhs[i,j] for all valid indices.
* Matrices must have identical dimensions.
*
* @throws std::invalid_argument if matrices have different dimensions
*/
Matrix& operator+=(const Matrix& rhs);
/**
* @brief Matrix subtraction assignment
*
* @param rhs Matrix to subtract from this matrix
* @return Reference to this matrix after subtraction
*
* Performs element-wise subtraction: this[i,j] -= rhs[i,j] for all valid indices.
* Matrices must have identical dimensions.
*
* @throws std::invalid_argument if matrices have different dimensions
*/
Matrix& operator-=(const Matrix& rhs);
/**
* @brief Matrix multiplication assignment
*
* @param rhs Matrix to multiply with this matrix
* @return Reference to this matrix after multiplication
*
* Performs matrix multiplication: this = this * rhs.
* Number of columns in this matrix must equal number of rows in rhs.
*
* @throws std::invalid_argument if matrix dimensions are incompatible
*/
Matrix& operator*=(const Matrix& rhs);
/**
* @brief Scalar multiplication assignment
*
* @param s Scalar value to multiply with
* @return Reference to this matrix after multiplication
*
* Multiplies each matrix element by the scalar: this[i,j] *= s for all elements.
*/
constexpr Matrix& operator*=(const T& s);
/**
* @brief Scalar division assignment
*
* @param s Nonzero scalar value to divide by
* @return Reference to this matrix after division
*
* Divides each matrix element by the scalar: this[i,j] /= s for all elements.
*
* @throws std::invalid_argument if attempting to divide by zero
*
* @warning Reliable results ( (M / s) * s == M for a matrix M and nonzero scalar s are only guaranteed in case T
* fulfills concept FieldType<T>
*/
Matrix& operator/=(const T& s);
/** @} */
/** @name Randomization
* @{
*/
/**
* @brief Fill matrix with random values
* @return Reference to this matrix after randomization
*
* Fills the matrix with random values appropriate for the component type:
* - **Finite fields**: Using field-specific randomization
* - **Signed integers**: Uniform random values in range [-100, 100]
* - **Complex numbers**: Real and imaginary parts uniform random in [-1.0, 1.0]
* - **Double**: Uniform random values in range [-1.0, 1.0]
*
* @note Matrix type becomes @ref details::Generic after randomization, actual structure is not checked
*/
Matrix& randomize();
/** @} */
/** @name Information and Properties
* @{
*/
/**
* @brief Get the number of rows
*
* @return Number of rows in the matrix
*/
constexpr size_t get_m() const noexcept { return m; }
/**
* @brief Get the number of columns
*
* @return Number of columns in the matrix
*/
constexpr size_t get_n() const noexcept { return n; }
/**
* @brief Check if matrix is empty
*
* @return true if matrix has zero rows or columns, false otherwise
*/
constexpr bool is_empty() const noexcept { return m == 0 || n == 0; }
/**
* @brief Check if matrix is zero
*
* Sets type to details::Zero in case the matrix is zero.
*
* @return true if matrix has only zero components, false otherwise
*
* @see @ref CECCO::details::matrix_type_t for matrix type optimizations
*/
constexpr bool is_zero() noexcept {
if (type == details::Zero) return true;
const bool b = std::ranges::all_of(data, [](const T& v) { return v == T(0); });
if (b) type = details::Zero;
return b;
}
/**
* @brief Check if matrix is zero
*
* @return true if matrix has only zero components, false otherwise
*/
constexpr bool is_zero() const noexcept {
if (type == details::Zero) return true;
return std::ranges::all_of(data, [](const T& v) { return v == T(0); });
}
/**
* @brief Compute Hamming weight (number of non-zero elements)
*
* @return Number of non-zero elements in the matrix
*
* Counts the number of elements that are not equal to T(0).
*
* @note Only for types fulfilling CECCO::ReliablyComparableType.
*/
constexpr size_t wH() const noexcept
requires ReliablyComparableType<T>;
/**
* @brief Compute matrix rank with caching
*
* @return Rank of the matrix (dimension of row/column space)
*
* Computes the rank using Gaussian elimination (REF algorithm).
* Uses caching for repeated calls.
*
* @note Only available for field types (requires division)
*/
size_t rank() const
requires FieldType<T>;
/**
* @brief Check if matrix is invertible
*
* @return true if matrix is square and has full rank, false otherwise
*
* @note Only available for field types
*/
bool is_invertible() const
requires FieldType<T>
{
return m == n && rank() == m;
}
/**
* @brief Extract the main diagonal as a vector
*
* @return Vector containing the diagonal elements
*
* Returns a vector containing the elements on the main diagonal. For square matrices only.
*
* @throws std::invalid_argument if matrix is not square
* @throws std::bad_alloc if memory allocation fails
*/
Vector<T> diagonal() const;
/**
* @brief Compute characteristic polynomial
*
* @return Characteristic polynomial det(λI - A)
*
* Computes the characteristic polynomial using the Samuelson-Berkowitz algorithm.
* For square matrices only. The result is a polynomial of degree m.
*
* @throws std::invalid_argument if matrix is not square or empty
*
* @note Specialized algorithms for structured matrices (@ref details:Diagonal, @ref details::Vandermonde)
* @note Only available for field types
*/
Polynomial<T> characteristic_polynomial() const
requires FieldType<T>;
/**
* @brief Compute basis for the nullspace (kernel)
*
* @return Matrix whose rows form a basis for the nullspace
*
* Computes a basis for the nullspace using Gaussian elimination.
* The nullspace consists of all row vectors x such that Ax^T = 0.
*
* @note Only available for field types
*/
Matrix<T> basis_of_nullspace() const
requires FieldType<T>;
/**
* @brief Compute basis for the kernel (alias for nullspace)
*
* @return Matrix whose rows form a basis for the kernel
*
* Equivalent to basis_of_nullspace(). The kernel and nullspace are
* the same mathematical concept.
*
* @note Only available for field types
*/
Matrix<T> basis_of_kernel() const
requires FieldType<T>
{
return basis_of_nullspace();
}
/**
* @brief Compute matrix determinant
*
* @return Determinant of the matrix
*
* Computes the determinant using algorithms based on matrix type.
* For square matrices only.
*
* @throws std::invalid_argument if matrix is not square or empty
*
* @note Returns T(0) for singular matrices
* @note Only available for field types that support division operations
*/
T determinant() const
requires FieldType<T>;
/**
* @brief Compute eigenvalues of the matrix
*
* @return Vector of eigenvalues
*
* Computes eigenvalues by finding roots of the characteristic polynomial.
* For square matrices only.
*
* @throws std::invalid_argument if matrix is not square
*
* @note Only available for finite field types
*/
std::vector<T> eigenvalues() const
requires FiniteFieldType<T>;
/**
* @brief Computes all vectors of the row space
*
* @return Container of all vectors of the row space
*
* @warning The row space can be exceedingly large!!
*
* @note Only available for field types
*/
std::vector<Vector<T>> rowspace() const
requires FieldType<T>;
/**
* @brief Compute span of matrix rows (alias for row space)
*
* @return Container of all vectors of the row space
*
* Equivalent to rowspace(). Computes the span of the matrix rows.
*
* @note Only available for field types
*/
std::vector<Vector<T>> span() const
requires FieldType<T>
{
return rowspace();
}
/** @} */
/** @name Component Access and Manipulation
* @{
*/
/**
* @brief Set component value using perfect forwarding
*
* @tparam U Type that can be converted to T
* @param i Row index (0-based)
* @param j Column index (0-based)
* @param c Value to forward into the component
* @return Reference to this matrix after modification
*
* Efficiently forwards the value into the specified component position.
* Handles both lvalue and rvalue references optimally.
*
* @throws std::invalid_argument if either index is out of bounds
*
* @note Matrix type may change decay after this operation
*/
template <typename U>
Matrix& set_component(size_t i, size_t j, U&& c)
requires std::convertible_to<std::decay_t<U>, T>;
/**
* @brief Access matrix element (const)
*
* @param i Row index (0-based)
* @param j Column index (0-based)
* @return Const reference to element at position (i ,j)
*
* Provides read-only access to matrix elements with bounds checking.
*
* @throws std::invalid_argument if indices are out of bounds
*/
const T& operator()(size_t i, size_t j) const;
/**
* @brief Extract a row as a vector
*
* @param i Row index to extract
* @return Vector containing the elements of row i
*
* Creates a new vector containing all elements from the specified row.
*
* @throws std::invalid_argument if row index is out of bounds
* @throws std::bad_alloc if memory allocation fails
*/
Vector<T> get_row(size_t i) const;
/**
* @brief Extract a column as a vector
*
* @param j Column index to extract
* @return Vector containing the elements of column j
*
* Creates a new vector containing all elements from the specified column. This implies that the column is
* transposed (since @ref Vector realizes only row vectors).
*
* @throws std::invalid_argument if column index is out of bounds
* @throws std::bad_alloc if memory allocation fails
*/
Vector<T> get_col(size_t j) const;
/**
* @brief Extract a submatrix
*
* @param i Starting row index
* @param j Starting column index
* @param h Height (number of rows) of submatrix
* @param w Width (number of columns) of submatrix
* @return Submatrix containing elements from the specified region
*
* Extracts a submatrix from the region [i:i+h, j:j+w).
*
* @throws std::invalid_argument if submatrix extends beyond matrix bounds
* @throws std::bad_alloc if memory allocation fails
*/
Matrix<T> get_submatrix(size_t i, size_t j, size_t h, size_t w) const;
/**
* @brief Set a submatrix region
*
* @param i Starting row index for placement
* @param j Starting column index for placement
* @param N Matrix to copy into this matrix
* @return Reference to this matrix after submatrix assignment
*
* Copies the contents of matrix N into this matrix starting at position (i, j).
* The target region must fit within this matrix's bounds.
*
* @throws std::invalid_argument if submatrix would extend beyond bounds
*
* @note Matrix type may change to details::Generic after this operation
*/
Matrix<T>& set_submatrix(size_t i, size_t j, const Matrix& N);
/**
* @brief Join another matrix horizontally (concatenate columns)
*
* @param other Matrix to join to the right
* @return Reference to this matrix after horizontal join
*
* Concatenates the columns of another matrix to the right of this matrix.
* The matrices must have the same number of rows.
*
* @throws std::invalid_argument if matrices have different numbers of rows
* @throws std::bad_alloc if memory allocation fails
*
* @code{.cpp}
* Matrix<int> A = {{1, 2}, {3, 4}}; // 2 × 2 matrix
* Matrix<int> B = {{5, 6}, {7, 8}}; // 2 × 2 matrix
* A.horizontal_join(B); // A becomes 2 × 4 matrix [[1,2,5,6], [3,4,7,8]]
* @endcode
*/
Matrix<T>& horizontal_join(const Matrix& other);
/**
* @brief Join another matrix vertically (concatenate rows)
*
* @param other Matrix to join below
* @return Reference to this matrix after vertical join
*
* Concatenates the rows of another matrix below this matrix.
* The matrices must have the same number of columns.
*
* @throws std::invalid_argument if matrices have different numbers of columns
* @throws std::bad_alloc if memory allocation fails
*
* @code{.cpp}
* Matrix<int> A = {{1, 2}, {3, 4}}; // 2 × 2 matrix
* Matrix<int> B = {{5, 6}, {7, 8}}; // 2 × 2 matrix
* A.vertical_join(B); // A becomes 4 × 2 matrix [[1,2], [3,4], [5,6], [7,8]]
* @endcode
*/
Matrix<T>& vertical_join(const Matrix& other);
/**
* @brief Join another matrix diagonally (block diagonal)
*
* @param other Matrix to join diagonally
* @return Reference to this matrix after diagonal join
*
* Creates a block diagonal matrix with this matrix in the upper-left
* and the other matrix in the lower-right. Off-diagonal blocks are zero.
*
* @throws std::bad_alloc if memory allocation fails
*
* @code{.cpp}
* Matrix<int> A = {{1, 2}, {3, 4}}; // 2 × 2 matrix
* Matrix<int> B = {{5, 6}, {7, 8}}; // 2 × 2 matrix
* A.diagonal_join(B); // A becomes 4 × 4 block diagonal matrix
* @endcode
*/
Matrix<T>& diagonal_join(const Matrix& other) noexcept;
/**
* @brief Compute Kronecker product with another matrix
*
* @param other Matrix to compute Kronecker product with
* @return Reference to this matrix after Kronecker product
*
* Computes the Kronecker product (tensor product) of this matrix with another.
* If this matrix is m × n and other is p × q, the result is mp × nq.
*
* @throws std::bad_alloc if memory allocation fails
*/
Matrix<T>& Kronecker_product(const Matrix& other);
/**
* @brief Swap two rows of the matrix
*
* @param i Index of first row to swap
* @param j Index of second row to swap
* @return Reference to this matrix after row swap
*
* Exchanges the contents of rows i and j.
*