Le moyen le plus rapide de trouver des paires propres d'une petite matrice non symétrique sur un GPU en mémoire partagée

9

J'ai un problème où j'ai besoin de trouver toutes les paires propres positives (car la valeur propre est positive) d'une petite matrice non symétrique (généralement inférieure à 60x60). Je peux arrêter de calculer lorsque la valeur propre est inférieure à un certain seuil. Je sais que les valeurs propres sont réelles. Des suggestions sur les algorithmes que je pourrais utiliser pour essayer d'obtenir les meilleures performances? Je dois faire plusieurs milliers de ces décompositions, donc la vitesse est importante.

Merci d'avance.

EDIT: J'ai besoin de le faire sur le GPU en mémoire partagée. Les matrices n'ont pas non plus nécessairement la même taille. Je ne connais aucune bibliothèque qui le fasse pour le moment. Des suggestions d'algorithmes qui seraient bien adaptés au problème seraient appréciées.

Kantoku
la source
1
Si je comprends bien, vous avez un noyau CUDA qui calcule des milliers de petites matrices en mémoire partagée, et vous n'êtes pas disposé à les copier dans la mémoire globale. Avant d'essayer de donner une réponse, il y a quelques points à clarifier. Dans CUDA, la durée de vie de la mémoire partagée est obligée de bloquer la durée de vie: combien de threads avez-vous pour chaque matrice à décomposer? Les performances extrêmes sont-elles vraiment importantes? (Comment les temps d'extraction des valeurs propres attendus se comparent-ils aux temps de génération de matrice?) Sur la base de quel argument vous savez que le système propre est réel? Le système eigens peut-il être défectueux?
Stefano M
Bonjour Stefano et merci pour ton commentaire. Pour l'instant, j'aurai le multiple le plus proche de la taille de la chaîne à la dimension de la matrice que je voudrais décomposer. Les temps de génération de matrice varient beaucoup, et il y a des cas où le temps de génération de matrice est plus cher, mais il existe de nombreuses situations où le temps de génération de matrice est inférieur à la décomposition. Je sais que les valeurs propres sont réelles en raison de la façon dont la matrice est générée. Je préfère ne pas entrer dans les détails ici, car cela nuirait à la question initiale. Enfin, oui, le système peut être défectueux.
Kantoku

Réponses:

3

Sans faire beaucoup de recherche, je vous recommande de consulter la bibliothèque MAGMA . Code disponible gratuitement avec un support continu. NVIDIA a reconnu MAGMA comme une "percée dans les solveurs pour les problèmes de valeurs propres".

Il existe également la bibliothèque CULA , qui est généralement un produit commercial, bien que récemment, elle ait été rendue gratuite pour un usage académique (voir les détails ici ).

Alexandre
la source
Merci pour ta réponse Alexandre. J'ai déjà étudié les deux bibliothèques, et pour autant que je sache, les fonctions sont appelées depuis l'hôte et la mémoire doit être dans la mémoire globale. Je crois que les frais généraux seraient trop pour justifier l'utilisation. Toutes ces matrices sont générées en mémoire partagée, utilisées dans le noyau puis supprimées. Je voudrais les garder là sans avoir à les remettre dans la mémoire globale. Même si je les y poussais, il y aurait toujours le problème d'appeler de nombreuses fonctions du noyau à partir de l'hôte (quoique dans plusieurs flux).
Kantoku
1
@Kantoku, oui, ces bibliothèques sont plus générales et stockent la matrice entière dans la mémoire globale. Si vos matrices sont dans la mémoire partagée, un seul SM peut y travailler, non? La mise en œuvre d'EVD devrait donc être assez simple.
Alexander
Oui, je l'imagine, c'est pourquoi je cherchais des algorithmes adaptés à la situation. Je ne suis pas trop familier avec evd non symétrique, donc je cherchais des suggestions.
Kantoku
@Kantoku (et Alexander). Les EVD non symétriques sont loin d'être simples, même dans le cas séquentiel. C'est toujours un domaine de recherche actif.
Jack Poulson
@JackPoulson Ah oui, vous avez raison, mais je (et je suppose qu'Alexander aussi) voulait dire qu'il serait simple d'appliquer un algorithme établi au problème, étant donné que de nombreuses simplifications peuvent être apportées lorsque nous prenons la taille et la nature de la matrice en considération. Le problème est: quel algorithme.
Kantoku
2

Utilisez les fonctions de LAPACK, il est peu probable que vous puissiez les battre dans votre propre implémentation.

Wolfgang Bangerth
la source
Salut Wolfgang. Merci pour la réponse, mais j'ai l'intention de l'implémenter sur un GPU utilisant CUDA et pour plusieurs milliers de ces minuscules matrices (où chaque bloc gère la décomposition d'une seule matrice), et les matrices ne sont pas nécessairement de la même taille, donc la mise en œuvre quelque chose moi-même qui utilise la mémoire partagée semble être mon seul choix. Une idée quel algorithme serait le mieux adapté à ces types de matrices? PS Merci pour les conférences deal.II que vous avez données au KAUST le semestre dernier. Je les ai appréciés :)
Kantoku
2
@Kantoku Vous devez ajouter ces détails dans votre question, sinon cela est trompeur.
Alexander
@Alexander J'ai mis à jour la question avec plus de détails. Merci pour la suggestion!
Kantoku
1
@Kantoku: Les GPU sont un peu au-delà de mon domaine, mais je suis sûr qu'il existe déjà des bibliothèques qui font ce que vous voulez (et en fait, je vois que d'autres réponses les lient déjà). Heureux d'apprendre que vous avez aimé mes cours!
Wolfgang Bangerth