Quel algorithme est performant pour la multiplication matricielle de matrices 4×4 de transformations affines

Wikipedia répertorie quatre algorithmes pour multiplication matricielle de deux matrices nxn .

Le classique quun programmeur écrirait est O (n ³ ) et est répertorié comme la « multiplication matricielle des manuels scolaires ». Ouais. O (n ³ ) est un peu un succès. Regardons le meilleur suivant.

L algorithme de Strassen est O (n ^2.807 ). Celui-ci fonctionnerait – il a quelques restrictions (comme la taille est une puissance de deux) et il a une mise en garde dans la description:

Par rapport à la multiplication matricielle conventionnelle, lalgorithme ajoute une charge de travail O (n ² ) considérable en addition / soustractions; donc en dessous dune certaine taille, il sera préférable dutiliser la multiplication conventionnelle.

Pour ceux qui sont intéressés par cet algorithme et ses origines, en regardant Comment Strassen a-t-il proposé sa méthode de multiplication matricielle? peut être une bonne lecture. Cela donne un indice sur la complexité de cette charge de travail initiale O (n ² ) qui est ajoutée et pourquoi cela coûterait plus cher que la simple multiplication classique.

Donc, cest vraiment est O (n ² + n ^2.807 ) avec ce bit sur lexposant inférieur n étant ignoré lors de lécriture du grand O. Il semble que si vous travaillent sur une belle matrice 2048×2048, cela pourrait être utile. Pour une matrice 4×4, elle va probablement la trouver plus lente car cette surcharge consomme tout le reste du temps.

Et puis il ya le Coppersmith – Winograd algorithme qui est O (n ^2.373 ) avec quelques améliorations. Il est également livré avec une mise en garde:

Lalgorithme Coppersmith – Winograd est fréquemment utilisé comme élément de base dans dautres algorithmes pour prouver les limites de temps théoriques. Cependant, contrairement à lalgorithme de Strassen, il nest pas utilisé en pratique car il ne fournit un avantage que pour les matrices si grandes quelles ne le peuvent pas être traité par du matériel moderne.

Donc, cest mieux quand vous travaillez sur des matrices de très grande taille, mais encore une fois, pas utile pour une matrice 4×4.

Cela se reflète à nouveau dans la page de wikipedia dans Multiplication matricielle: algorithmes sous-cubiques qui explique pourquoi les choses fonctionnent plus vite:

Il existe des algorithmes qui pr ovide de meilleurs temps de fonctionnement que les simples. Le premier à être découvert est lalgorithme de Strassen, conçu par Volker Strassen en 1969 et souvent appelé « multiplication matricielle rapide ». Il est basé sur une méthode de multiplication de deux matrices 2 × 2 qui ne nécessite que 7 multiplications (au lieu de lhabituel 8), au prix de plusieurs opérations additionnelles daddition et de soustraction. Lapplication récursive donne un algorithme avec un coût multiplicatif de O (n ^{log ₂ 7} ) ≈ O (n ^2.807 ). Lalgorithme de Strassen est plus complexe et la stabilité numérique est réduite par rapport à lalgorithme naïf, mais il est plus rapide dans les cas où n> 100 environ et apparaît dans plusieurs bibliothèques, telles que BLAS.

Et cela va au cœur de la raison pour laquelle les algorithmes sont plus rapides – vous faites un compromis une certaine stabilité numérique et une configuration supplémentaire. Cette configuration supplémentaire pour une matrice 4×4 est bien plus que le coût de multiplication.

Et maintenant, pour répondre à votre question:

Mais existe-t-il des algorithmes particulièrement efficaces pour des matrices aussi petites?

Non, il ny a pas dalgorithme optimisé pour la multiplication matricielle 4×4 car celui en O (n ³ ) fonctionne assez raisonnablement jusquà ce que vous commenciez à découvrir que vous êtes prêt à prendre un gros coup pour les frais généraux. Pour votre situation spécifique, il peut y avoir des frais généraux que vous pourriez encourir en sachant à lavance des choses spécifiques sur vos matrices (comme la quantité de données réutilisées), mais la chose la plus simple à faire est décrire un bon code pour le O (n ³ ), laissez le compilateur le gérer et profilez-le plus tard pour voir si vous avez réellement le code qui est le point lent dans la multiplication de la matrice.

Related on Math.SE: Nombre minimal de multiplications requis pour inverser une matrice 4×4

Souvent, les algorithmes simples sont les plus rapides pour les très petits ensembles, car les algorithmes plus complexes utilisent généralement une transformation qui ajoute une surcharge. Je pense que votre meilleur pari nest pas sur un algorithme plus efficace (je pense que la plupart des bibliothèques utilisent des méthodes simples), mais sur une implémentation plus efficace, par exemple, une implémentation utilisant des extensions SIMD (en supposant le code x86 ou amd64), ou écrite à la main en assemblage . En outre, la disposition de la mémoire doit être bien pensée. Vous devriez être en mesure de trouver suffisamment de ressources à ce sujet.

Pour la multiplication 4×4 mat / mat, les améliorations algorithmiques sont souvent absentes . Lalgorithme de base de complexité en temps cubique a tendance à très bien se comporter, et tout ce qui est plus sophistiqué est plus susceptible de dégrader que daméliorer les temps. En général, les algorithmes sophistiqués ne conviennent pas sil ny a pas de facteur dévolutivité impliqué (par exemple, essayer de trier rapidement un tableau qui a toujours 6 éléments par opposition à une simple insertion ou un tri par bulles). des choses comme la transposition de matrice ici pour améliorer la localité de référence naident pas non plus réellement la localité de référence lorsquune matrice entière peut tenir dans une ou deux lignes de cache. À ce type déchelle miniature, si vous effectuez une multiplication de tapis / tapis 4×4 en masse, les améliorations viendront généralement doptimisations au micro-niveau des instructions et de la mémoire, comme un alignement correct des lignes de cache.

Commentaires

• Excellente réponse! Je ‘ nai jamais entendu parler de lacronyme SoA (du moins, en néerlandais, cest un acronyme pour ‘ seksueel overdraagbare aandoening ‘ qui signifie ‘ maladie sexuellement transmissible ‘ … mais que ‘ s espérons pas ce que vous entendez ici). La technique semble claire, je ‘ m même assez surpris quil y ait un nom pour cela. Que signifie SoA?
• @Ruben Structure of Arrays par opposition à Arrays of Structures. Les SoA peuvent également être des PITA – mieux enregistrés pour vos chemins les plus critiques. Voici ‘ un joli petit lien que jai trouvé sur le sujet: stackoverflow.com/questions/17924705/…
• Vous voudrez peut-être mentionner C ++ 11 / C11 alignas .

Si vous savez avec certitude que vous naurez besoin que de multiplier 4×4 matrices, alors vous navez pas du tout à vous soucier dun algorithme général. Vous pouvez simplement prendre deux pointeurs et utiliser ceci:

(Je recommande fortement de traduire ceci de manière automatisée).

Le compilateur serait alors positionné de manière optimale pour optimiser ce code (pour réutiliser des sommes partielles, réorganiser les mathématiques, etc.) car il peut tout voir, il ny a pas de boucles dynamiques et pas de flux de contrôle.

Difficile dimaginer que cela puisse être battu sans en utilisant des intrinsèques.

Vous ne pouvez pas comparer directement la complexité asymptotique si vous définissez n différemment. Vous êtes habitué à comparer la complexité des algorithmes sur des structures de données plates comme des listes, où n est défini comme étant le nombre total déléments dans la liste, mais les algorithmes matriciels définissent n comme étant seulement la longueur dun côté .

Par cette définition de n, quelque chose daussi simple que de regarder chaque élément une fois pour limprimer, ce que vous pensez normalement comme O (n), est O (n ² ) . Si vous définissez n comme le nombre total déléments de la matrice, cest-à-dire n = 16 pour une matrice 4×4, alors la multiplication matricielle naïve est seulement O (n ^1,5 ), ce qui est plutôt bien.

Votre meilleur pari est de tirer parti du parallélisme en utilisant des instructions SIMD ou un GPU, plutôt que dessayer daméliorer lalgorithme basé sur la croyance erronée que O (n ³ ) est aussi mauvais que ce serait si n était défini de manière comparable à une structure de données plate.