Le but du stage sera de dévélopper et d'évaluer l’algorithme de décomposition polaire ZOLO à grande échelle au sein de la bibliothèque Chameleon.
La résolution des problèmes aux valeurs propres/singulières est un problème très complexe et fourmand en calculs lorsque l’on cherche à calculer l’ensemble de toutes les valeurs propres du systèmes. De plus, l’algorithme de référence est très difficilement parallélisable et est principalement consommateur de mémoire et de bande bassante lui conférant une très faible scalabilité. Une alternatve consiste à utiliser des algorithmes plus coûteux, voire beaucoup plus coûteux, mais plus facilement parallélisable, ce qui permet de réduire le temps d’obtention de la solution. Parmi ces algorithmes, on retrouve la décomposition polaire qui permet ensuite de trouver la décomposition SVD.
Le premier algorithme de ce type: l’algorithme QR-based Dynamically Weighted Halley (QDWH) a déjà été implémenté au dessus de supports d’exécutions: PaRSEC/Distributed Memory, StarPU/Heterogeneous. Cependant cet algorithme manque également de scalabilité à très grande échelle. Un algorithme encore plus coûteux en calcul: l’algorithme ZOLO a été implémenté par la même équipe de KAUST à l’aide de la bibliothèque standard ScaLAPACK et a démontré de très bonne scalabilité à très grande échelle. (cf ici). Malheureusement, en plus d'être très coûteux en calcul, cet algorithme est également coûteux en mémoire. L’utilisation de support d’exécution permettrait de faire de l’allocation mémoire à la volée et de pouvoir se débarasser des matrices temporaires aussitôt que possible. Pour cela, un début d’implémentation a été fait au sein de la bibliothèque Chameleon.
Le but du stage sera de développer l’algorithme de décomposition polaire ZOLO au dessus de la bibliothèque Chameleon. Le développement nécessitera de bien comprendre l’algorithme et les problèmes d’algèbre linéaire dense, ainsi que les techniques permettant de les paralléliser. La validation des travaux de stage se fera sur la plate-forme de calcul de l’Inria Bordeaux et sur le supercalculateur Shaheen-II de KAUST (King Abdullah University of Science and Technology).
dense linear algebra, task-based programming, runtime systems