Résolution répétée de

12

J'utilise MATLAB pour résoudre un problème qui implique de résoudre à chaque pas de temps, où change avec le temps. En ce moment, j'accomplis ceci en utilisant MATLAB :bAx=bbmldivide

x = A\b

J'ai la flexibilité de faire autant de précalculs que nécessaire, donc je me demande s'il existe une méthode plus rapide et / ou plus précise que mldivide. Que fait-on généralement ici? Merci a tous!

Doute
la source
1
Avez-vous des connaissances spécifiques sur la structure de ? Par exemple, est-ce symétrique? Définie positive? Tridiagonal? Orthogonal? A
Dominique
La matrice est une matrice carrée dense. A
Doubt
3
Si vous n'avez aucune autre connaissance sur , la factorisation comme décrit dans la réponse ci-dessous est votre meilleur pari. L UALU
Dominique

Réponses:

14

La chose la plus évidente que vous pouvez faire est de précalculer

[L,U] = lu(A) ~ O (n ^ 3)

Ensuite, vous calculez

x = U \ (L \ b) ~ O (2 n ^ 2)

Cela réduirait considérablement le coût et le rendrait plus rapide. La précision serait la même.

Milind R
la source
1
Notez, d'après la documentation , que L n'est pas nécessairement triangulaire inférieur. Cette réponse serait probablement plus rapide qu'une résolution directe, mais je veillerais à ce que la commande L \ b soit suffisamment intelligente pour savoir résoudre L dans le bon ordre (c'est probablement le cas, mais cela ne dit pas avec certitude dans la documentation).
Godric Seer
Oui, vous avez raison, L est le produit d'une matrice triangulaire inférieure et d'une matrice de permutation. Mais je serai damné s'il ne reconnaît pas que tout ce qu'il a à faire, c'est une substitution en arrière avec L\b. Parce que j'ai vu cette ligne exacte utilisée dans le code haute performance par ceux que je considère comme des experts.
Milind R
8
mldivide reconnaît les matrices triangulaires permutées et fait la bonne chose pour résoudre un tel système. Cependant, dans mes expériences, cela semble ralentir le processus de résolution d'un facteur de 10 environ pour une matrice de taille 2000 par 2000 à 10000 par 10000. Ainsi, vous feriez mieux de garder une trace explicite de la permutation en utilisant [L , U, P] = lu (P). O(n2)
Brian Borchers
1
De plus, si votre matrice est clairsemée, vous devez profiter de la rareté de la résolution du système. La façon la plus simple de procéder consiste à vous assurer que est stocké au format clairsemé en utilisant A = clairsemé (A) avant de calculer la factorisation LU. Vous pouvez également essayer de permuter les lignes de A afin de réduire le remplissage lors de la factorisation LU. A
Brian Borchers
3
@BrianBorcher Pour autant que je sache, la meilleure façon de suivre la permutation est de [L,U,p] = lu(A,'vector'); x = U\(L\b(p));voir l'exemple 3 dans la lu documentation .
Stefano M
5

Nous avons fait de nombreux laboratoires informatiques dans nos cours de calcul scientifique sur ce sujet. Pour les "petits" calculs que nous y avons faits, l'opérateur de barre oblique inverse de Matlab était toujours plus rapide que toute autre chose, même après avoir optimisé notre code autant que possible et réorganisé toutes les matrices au préalable (par exemple avec Reverse Cuthill McKee commandant des matrices clairsemées) .

Vous pouvez consulter l'une de nos instructions de laboratoire . La réponse à votre question est couverte (sous peu) à la page 4.

Un bon livre sur le sujet est écrit par exemple par Cheney .

Seb
la source
4

An×n Axi=bii=1mm

V = inv(A);
...
x = V*b;

O(n3)inv(A)O(n2)V*bm

>> n = 5000;
>> A = randn(n,n);
>> x = randn(n,1);
>> b = A*x;
>> rcond(A)
ans =
   1.3837e-06
>> tic, xm = A\b; toc
Elapsed time is 1.907102 seconds.
>> tic, [L,U] = lu(A); toc
Elapsed time is 1.818247 seconds.
>> tic, xl = U\(L\b); toc
Elapsed time is 0.399051 seconds.
>> tic, [L,U,p] = lu(A,'vector'); toc
Elapsed time is 1.581756 seconds.
>> tic, xp = U\(L\b(p)); toc
Elapsed time is 0.060203 seconds.
>> tic, V=inv(A); toc
Elapsed time is 7.614582 seconds.
>> tic, xv = V*b; toc     
Elapsed time is 0.011499 seconds.
>> [norm(xm-x), norm(xp-x), norm(xl-x), norm(xv-x)] ./ norm(x)
ans =
   1.0e-11 *
    0.1912    0.1912    0.1912    0.6183

A1LUm>125

Quelques notes

Pour la stabilité et l'analyse des erreurs, veuillez consulter les commentaires de cette réponse différente , en particulier celle de VictorLiu.

mn

La synchronisation a été effectuée avec Matlab R2011b sur un ordinateur à 12 cœurs avec une moyenne de charge UNIX assez constante de 5; meilleur tic, toctemps de trois sondes.

Stefano M
la source
En effet, il y a beaucoup plus de parallélisme disponible dans une multiplication matrice-vecteur qu'un solveur triangulaire, donc cela devrait être encore plus apparent si les calculs sont effectués en parallèle (multicœur / GPU / etc ...) de quelque manière que ce soit.
Aron Ahmadia
@AronAhmadia Je suis d'accord: les estimations du seuil de rentabilité basées uniquement sur le nombre d'opérations n'ont de sens que pour une implémentation en série.
Stefano M
1
Notez que les choses seront très différentes si la matrice A est clairsemée - l'inverse sera généralement assez dense, tandis que les facteurs LU sont généralement raisonnablement clairsemés, faisant basculer les choses dans le sens de LU étant plus rapide.
Brian Borchers
1
A
1
inv(A)Ax=bbBA\B
2

Jetez un œil à cette question , les réponses montrent qu'elle mldivideest assez intelligente et donne également des suggestions sur la façon de voir ce que Matlab utilise pour résoudre A\b. Cela peut vous donner un indice concernant les options d'optimisation.

Psirus
la source
0

L'utilisation de la barre oblique inverse est plus ou moins équivalente à inv(A)*B, si vous la codez librement, cette dernière pourrait être plus intuitive. Ils sont à peu près les mêmes (juste différents dans la façon dont le calcul est effectué), bien que vous devriez vérifier la documentation de Matlab pour des éclaircissements.

Pour répondre à votre question, la barre oblique inverse est généralement correcte, mais elle dépend des propriétés de la matrice de masse.

AlanH
la source
1
Mathématiquement inv (A) * b est le même que \ cependant numériquement, la formation de l'inverse est à la fois moins efficace et moins précise. Si vous travaillez pour apprendre l'algèbre linéaire, cela peut être acceptable, mais je dirais que vous avez besoin d'une très bonne raison pour former l'inverse.
Godric Seer
Mais pourquoi voudriez-vous jamais calculer inv(A)puisque cela seul est plus cher que A\b?
Dominique
7
@Godric: Il y a un article récent qui discute du "mythe" selon lequel inv (A) * b est moins précis: sur ArXiv . Ne pas dire qu'il y a généralement des raisons de calculer l'inverse réel, mais simplement dire.
Victor Liu
3
@Dominique: Les résolutions triangulaires sont beaucoup moins parallélisables que la multiplication matrice-vecteur, et les méthodes itératives préconditionnées sophistiquées utilisent souvent des méthodes directes sur les sous-domaines. Il est souvent utile de former explicitement les inverses de quelques matrices triangulaires denses de taille modeste afin d'améliorer le parallélisme.
Jack Poulson
@VictorLiu: Merci pour l'article. Je me tiens corrigé sur ma déclaration de précision (au moins pour les implémentations intelligentes de inv (A)).
Godric Seer