A Symmetry Preserving Algorithm for Matrix Scaling

Résumé : Nous décrivons un algorithme itératif qui, asymptotiquement, met une matrice à l'échelle de telle sorte que chaque ligne et chaque colonne est de taille 1 dans la norme infini. Cet algorithme préserve la symétrie. De plus, il converge assez rapidement avec un taux asymptotique de 1/2. Nous discutons la généralisation de l'algorithme à la norme 1 et, par inférence, à d'autres normes. Pour le cas de la norme 1, nous établissons que l'algorithme converge avec un taux linéaire. Nous démontrons expérimentalement que notre algorithme améliore le conditionnement de la matrice et qu'il aide les méthodes directes de résolution en réduisant le pivotage. Particulièrement pour des matrices symétriques, nos résultats théoriques et expérimentaux mettent en valeur l'intérêt de notre algorithme par rapport aux algorithmes existants.
Type de document :
Article dans une revue
SIAM Journal on Matrix Analysis and Applications, Society for Industrial and Applied Mathematics, 2014, 35 (3), pp.25. 〈10.1137/110825753〉
Liste complète des métadonnées

Littérature citée [30 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00569250
Contributeur : Bora Uçar <>
Soumis le : vendredi 30 janvier 2015 - 09:47:50
Dernière modification le : mardi 16 janvier 2018 - 16:10:18
Document(s) archivé(s) le : jeudi 10 septembre 2015 - 16:10:25

Fichier

symmetryPreservingScaling-8257...
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Philip A. Knight, Daniel Ruiz, Bora Uçar. A Symmetry Preserving Algorithm for Matrix Scaling. SIAM Journal on Matrix Analysis and Applications, Society for Industrial and Applied Mathematics, 2014, 35 (3), pp.25. 〈10.1137/110825753〉. 〈inria-00569250v4〉

Partager

Métriques

Consultations de la notice

358

Téléchargements de fichiers

812