matrix — Enter the Matrix

Une bibliotheque d'algebre lineaire ecrite from scratch en C++17, templatee sur le corps des scalaires : elle tourne aussi bien sur les reels que sur les complexes.

Projet 42 « matrix » Aucune bibliotheque d'algebre externe : tout — du produit scalaire au pivot de Gauss — est reimplemente a la main, avec les bornes de complexite imposees par le sujet.

• Ce que fait le projet
• Build & run
• Les 14 exercices
• L'API
• Le mode complexe
• Fused Multiply-Add

Vector<K> et Matrix<K> sont generiques sur le type scalaire K. Le projet instancie deux corps :

La meme ligne de code calcule donc un determinant reel ou complexe. Ce n'est pas gratuit : le produit scalaire devient hermitien (somme u_i * conj(v_i)), la norme passe par abs() du module, et les comparaisons de pivots se font sur des modules et non sur des valeurs signees. Ces pieges sont commentes directement dans le code, au-dessus des fonctions concernees.

make            # compile -> ./matrix
make re         # rebuild complet
make fclean

./matrix        # tous les exercices, version reelle
./matrix -c     # tous les exercices, version complexe
./matrix 09     # un seul exercice (00..13)
./matrix 09 -c  # un seul exercice, version complexe

Exemple :

$ ./matrix 09
-----------------EX09-----------------------
transpose test 1
[[-2, 1, 0]
[-8, -23, 6]
[4, 4, 4]]

[[-2, -8, 4]
[1, -23, 4]
[0, 6, 4]]

Flags imposes : -Wall -Wextra -Werror -std=c++17. Le build doit rester sans aucun warning.

Le bonus ex15 — espaces vectoriels complexes n'est pas un exercice separe ici : c'est le drapeau -c, qui rejoue tous les exercices sur K = Complex.

Chaque exercice est explique — theorie, piege, choix d'implementation — dans le carnet HTML.

template <class K>
class Vector {
    void      add(const Vector &other);
    void      sub(const Vector &other);
    void      scl(const K &s);
    K         dot(const Vector &other) const;   // hermitien si K = Complex
    _Float32  norm_1() const;                   // somme des |u_i|
    _Float32  norm() const;                     // euclidienne
    _Float32  norm_inf() const;                 // max des |u_i|
};

template <class K>
class Matrix {
    void              add(const Matrix &other);
    void              sub(const Matrix &other);
    void              scl(const K &s);
    Vector<K>         mul_vec(const Vector<K> &v) const;
    Matrix<K>         mul_mat(const Matrix<K> &m);
    K                 trace() const;
    Matrix<K>         transpose() const;
    Matrix<K>         row_echelon();
    K                 determinant();
    Matrix<K>         inverse();
    size_t            rank();

    std::array<unsigned long, 2> getShape() const;
    bool                         isSquare() const;
};

Les deux classes se construisent depuis un std::vector (std::vector<K> pour Vector, std::vector<std::vector<K>> pour Matrix, dont l'homogeneite des lignes est verifiee), s'indexent par operator[] et s'affichent via operator<<.

Complex est un scalaire complet : operateurs arithmetiques, comparaisons, affichage, plus les surcharges non qualifiees abs(), conj() et fma() que Vector et Matrix appellent par ADL. C'est ce mecanisme qui rend le code generique reellement generique : pour un K reel, conj() est l'identite et tout retombe sur les formules usuelles, sans une seule branche if.

⚠️ std::is_arithmetic<_Float32> vaut false sous GCC. D'ou les surcharges non-template abs(_Float32) / conj(_Float32) dans Complex.hpp — les supprimer casse la compilation du mode reel.

Le sujet n'autorise fma comme seule fonction mathematique sur la plupart des exercices. Toutes les accumulations du projet passent donc par fma(). Quatre modes de build :

make                  # fma(), compile en a * b + c — portable, defaut
make FMA=1 OPT=-O2    # -mfma : vfmadd132ss / vfmadd231ss, un seul arrondi
make FORCE_FMA=1      # appel libc a arrondi correct, sans exiger -mfma
make NOFMA=1          # code d'origine, ecrit sans fma du tout

• -mfma exige un CPU Haswell+ (2013) ; sinon SIGILL. Ce n'est donc pas le defaut.
• Sans -O, les fma() restent des appels de fonction et -mfma ne sert a rien. Mesure sur main.o : -O2 seul donne des mulss/addss, -O2 -mfma donne 27 vfmadd* et aucun appel.
• Changer de mode recompile tout automatiquement (stamp .cxxflags).

Les deux ecritures — avec et sans fma — coexistent dans les fichiers, separees par #if defined(MATRIX_NO_FMA). Toute modification d'une branche doit etre reportee dans l'autre, sinon make NOFMA=1 et make divergent.