Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Matrice creuse
Résumé
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. Ce concept de matrice creuse est très utilisé en analyse combinatoire et ses domaines d'applications tels que la théorie des réseaux, qui ont une faible densité de connexions.
Des matrices creuses de taille importante apparaissent souvent en science ou en ingénierie pour la résolution des équations aux dérivées partielles.
Quand on veut manipuler ou stocker des matrices creuses à l'aide de l'outil informatique, il est avantageux voire souvent nécessaire d'utiliser des algorithmes et des structures de données qui prennent en compte la structure peu dense de la matrice : dès lors que des coordonnées de ligne et de colonne donnent accès à une adresse, peu importe l'organisation physique des données.
Représenter physiquement tous ces zéros en mémoire quand ils sont utilisés sur de grandes matrices creuses serait coûteux et lent. Il est plus économique et plus rapide de dire que toute valeur non renseignée pour des coordonnées données est zéro. Cette compression de données amène presque toujours à une division importante de la consommation de mémoire, pour un surcoût négligeable de traitement. Certaines matrices creuses de très grande taille ne sont toutefois pas manipulables par les algorithmes classiques.
La structure de données naïve utilisée pour stocker une matrice est un tableau bidimensionnel. Chaque entrée du tableau représente un élément ai, j de la matrice qui peut être atteint par les deux indices i et j. Pour une matrice m×n il faut au moins (m×n) espaces mémoire de taille fixe pour représenter la matrice.
Source officielle
À 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.
Proximité ontologique
Cours associés (21)
COM-406: Foundations of Data Science
We discuss a set of topics that are important for the understanding of modern data science but that are typically not taught in an introductory ML course. In particular we discuss fundamental ideas an
MATH-453: Computational linear algebra
This course provides an overview of advanced techniques for solving large-scale linear algebra problems, as they typically arise in applications. A central goal of this course is to give the ability t
EE-726: Sparse stochastic processes
We cover the theory and applications of sparse stochastic processes (SSP). SSP are solutions of differential equations driven by non-Gaussian innovations. They admit a parsimonious representation in a
Séances de cours associées (70)
Méthode du gradient conjugué : résoudre des systèmes linéaires
Couvre la méthode Conjugate Gradient pour résoudre des systèmes linéaires sans préconditionnement, en explorant les implémentations de calcul parallèle et les prédictions de performances.
Systèmes linéaires : méthodes directes
Explore les systèmes linéaires, l'élimination gaussienne, la décomposition LU et les types matriciels.
Produit commandé normal et théorème de Wick
Couvre le produit ordonné normal, le théorème de Wick, les champs de création et de destruction et la méthodologie de calcul efficace.
Publications associées (226)
A 16-bit Floating-Point Near-SRAM Architecture for Low-power Sparse Matrix-Vector Multiplication
David Atienza Alonso, Giovanni Ansaloni, Grégoire Axel Eggermann, Marco Antonio Rios
State-of-the-art Artificial Intelligence (AI) algorithms, such as graph neural networks and recommendation systems, require floating-point computation of very large matrix multiplications over sparse data. Their execution in resource-constrained scenarios, ...
2023Personnes associées (35)
Unités associées (5)
Concepts associés (18)
Matrice (mathématiques)
thumb|upright=1.5 En mathématiques, les matrices sont des tableaux d'éléments (nombres, caractères) qui servent à interpréter en termes calculatoires, et donc opérationnels, les résultats théoriques de l'algèbre linéaire et même de l'algèbre bilinéaire. Toutes les disciplines étudiant des phénomènes linéaires utilisent les matrices. Quant aux phénomènes non linéaires, on en donne souvent des approximations linéaires, comme en optique géométrique avec les approximations de Gauss.
Valeur propre, vecteur propre et espace propre
En mathématiques, et plus particulièrement en algèbre linéaire, le concept de vecteur propre est une notion algébrique s'appliquant à une application linéaire d'un espace dans lui-même. Il correspond à l'étude des axes privilégiés, selon lesquels l'application se comporte comme une dilatation, multipliant les vecteurs par une même constante. Ce rapport de dilatation est appelé valeur propre, les vecteurs auxquels il s'applique s'appellent vecteurs propres, réunis en un espace propre.
Factorisation de Cholesky
La factorisation de Cholesky, nommée d'après André-Louis Cholesky, consiste, pour une matrice symétrique définie positive , à déterminer une matrice triangulaire inférieure telle que : . La matrice est en quelque sorte une « racine carrée » de . Cette décomposition permet notamment de calculer la matrice inverse , de calculer le déterminant de A (égal au carré du produit des éléments diagonaux de ) ou encore de simuler une loi multinormale. Elle est aussi utilisée en chimie quantique pour accélérer les calculs (voir Décomposition de Cholesky (chimie quantique)).
MOOCs associés (23)
Digital Signal Processing [retired]
The course provides a comprehensive overview of digital signal processing theory, covering discrete time, Fourier analysis, filter design, sampling, interpolation and quantization; it also includes a
Digital Signal Processing I
Basic signal processing concepts, Fourier analysis and filters. This module can
be used as a starting point or a basic refresher in elementary DSP
Digital Signal Processing II
Adaptive signal processing, A/D and D/A. This module provides the basic
tools for adaptive filtering and a solid mathematical framework for sampling and
quantization