Publication

MATHICSE Technical Report : A fast spectral divide-and-conquer method for banded matrices

2018
Working Papers

Résumé

Based on the spectral divide-and-conquer algorithm by Nakatsukasa and Higham [SIAM J. Sci. Comput., 35(3):A1325{A1349, 2013], we propose a new algorithm for computing all the eigenvalues and eigenvectors of a symmetric banded matrix. For this purpose, we combine our previous work on the fast computation of spectral projectors in the so called HODLR format, with a novel technique for extracting a basis for the range of such a HODLR matrix. The numerical experiments demonstrate that our algorithm exhibits quasilinear complexity and allows for conveniently dealing with large-scale matrices.

Source officielle

https://infoscience.epfl.ch/entities/publication/cc92ba29-9a41-45f3-bdf5-371f07c05edc

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Graph Chat

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

2018
Working Papers

Résumé

Source officielle

https://infoscience.epfl.ch/entities/publication/cc92ba29-9a41-45f3-bdf5-371f07c05edc

À propos de ce résultat

Concepts associés (32)

Matrice creuse

Dans la discipline de l'analyse numérique des mathématiques, une matrice creuse est une matrice contenant beaucoup de zéros. Conceptuellement, les matrices creuses correspondent aux systèmes qui sont peu couplés. Si on considère une ligne de balles dont chacune est reliée à ses voisines directes par des élastiques, ce système serait représenté par une matrice creuse. Au contraire, si chaque balle de la ligne est reliée à toutes les autres balles, ce système serait représenté par une matrice dense.

Matrice bande

En mathématiques, une matrice bande ou une matrice à bande est une matrice creuse dont les coefficients non nuls sont restreints à une bande diagonale, comprenant la diagonale principale et éventuellement une ou plusieurs diagonales de chaque côté. Formellement, on considère une matrice carrée A =(ai,j). Si tous les éléments de la matrice sont nuls en dehors d'une bande diagonale dont la plage est déterminée par les constantes k1 et k2 : alors les quantités k 1 et k 2 sont appelées les largeurs de bande inférieure et largeur de bande supérieure respectivement.

Skyline matrix

In scientific computing, skyline matrix storage, or SKS, or a variable band matrix storage, or envelope storage scheme is a form of a sparse matrix storage format matrix that reduces the storage requirement of a matrix more than banded storage. In banded storage, all entries within a fixed distance from the diagonal (called half-bandwidth) are stored. In column-oriented skyline storage, only the entries from the first nonzero entry to the last nonzero entry in each column are stored.

Afficher plus

Publications associées (1)

MATHICSE Technical Report : A fast spectral divide-and-conquer method for banded matrices

Chattez avec Graph Search

Optimistic Active Replication