Solveur linéaire clairsemé pour de nombreux côtés droit

12

Je dois résoudre le même système linéaire clairsemé (300x300 à 1000x1000) avec de nombreux côtés droits (300 à 1000). En plus de ce premier problème, je voudrais également résoudre différents systèmes, mais avec les mêmes éléments non nuls (juste des valeurs différentes), c'est-à-dire de nombreux systèmes clairsemés avec un motif de rareté constant. Mes matrices sont indéfinies.

Les performances de la factorisation et de l'initialisation ne sont pas importantes, mais les performances de l'étape de résolution le sont. Actuellement, j'envisage PaStiX ou Umfpack, et je vais probablement jouer avec Petsc (qui prend en charge les deux solveurs) Existe-t-il des bibliothèques capables de tirer parti de mes besoins spécifiques (vectorisation, multi-threading) ou devrais-je compter sur des solveurs généraux, et peut-être les modifier légèrement pour mes besoins?

Et si la matrice clairsemée est plus grande, jusqu'à ? $10^6 \times 10^6$

linear-algebra petsc linear-solver sparse-matrix nat chouf
la source

10

Sans prendre parti pour la discussion sur l'opportunité d'utiliser des solveurs directs ou itératifs, je veux juste ajouter deux points:

Il existe des méthodes Krylov pour les systèmes à plusieurs côtés droits (appelées méthodes Krylov par blocs ). En prime, elles ont souvent une convergence plus rapide que les méthodes Krylov standard car l'espace Krylov est construit à partir d'une plus grande collection de vecteurs. Voir Dianne P. O'Leary, The Block Conjugate Gradient Algorithm and Related Methods . Algèbre linéaire et ses applications 29 (1980), pages 239-322. et Martin H. Gutknecht, Méthodes spatiales Block Krylov pour les systèmes linéaires avec plusieurs côtés droits: une introduction (2007).
Si vous avez différentes matrices avec le même motif de densité, vous pouvez précalculer une factorisation symbolique pour la première matrice, qui peut être réutilisée dans le calcul de la factorisation numérique pour cette matrice et les matrices suivantes. (Dans UMFPACK, vous pouvez le faire en utilisant umfpack di symbolicet en transmettant le résultat à umfpack_di_numeric.)

Christian Clason
la source

9

$O(N)$

Wolfgang Bangerth
la source

4

O (N^{2})

$O(N^2)$

O (N^{4 / 3})

$O(N^{4/3})$

O (N^{4 / 3})

$O(N^{4/3})$

N

$N$

3

O (N)

$O(N)$

O (N^{4 / 3})

$O(N^{4/3})$

2

10^{5}

$10^5$

n < 300 k

$n<300k$

3

Vous n'êtes pas tout à fait clair dans votre énoncé du problème lorsque vous parlez des "mêmes éléments non nuls (juste des valeurs différentes)". Êtes-vous en train de dire que la matrice a un modèle de densité constante mais que les valeurs réelles changent? Ou, dites-vous que la matrice est en fait constante?

$PA=LU$ $O(n^2)$

Pour plusieurs côtés droits et systèmes d'équations de cette taille, les méthodes itératives ne valent généralement pas la peine.

Tous les packages que vous avez mentionnés proposent des méthodes de factorisation directe (bien que PetSc soit surtout connu pour ses solveurs itératifs.) Cependant, vos systèmes sont si petits qu'il est peu probable que vous puissiez obtenir des accélérations parallèles substantielles, en particulier dans un environnement de mémoire distribuée.

Je suggère d'utiliser Umfpack pour ce travail - PaStix et PetSc sont exagérés.

Brian Borchers
la source

Merci pour votre réponse. Afin de clarifier: j'ai demandé d'abord une matrice unique avec de nombreux côtés droits, puis, un autre problème est une collection de matrices avec le même motif de rareté mais les valeurs changent, chacune d'elles doit être résolue pour de nombreuses rhs. Question subsidiaire: que se passe-t-il si la matrice clairsemée est maintenant de 10 ^ 5x10 ^ 5 à 10 ^ 6x10 ^ 6?

nat chouf

2

10^{5}

$10^5$

L'utilisation d'une méthode itérative pour vos grands systèmes avec un seul côté droit peut être utile, en particulier si vous n'avez pas besoin de solutions très précises et en particulier si vous pouvez trouver un préconditionneur efficace ou si vos systèmes sont déjà bien conditionnés. Cependant, si vos systèmes sont mal conditionnés, vous avez besoin de solutions précises et vous ne pouvez pas trouver un bon préconditionneur, alors vous serez probablement mieux avec la factorisation directe.

Brian Borchers

N

$N$

10^{6}

$10^6$

Solveur linéaire clairsemé pour de nombreux côtés droit

Réponses: