Discussion :

[Alexis.M]

Bonjour,

Je souhaite calculer les vecteurs propres et valeurs propres du laplacien d'un graphe correspondant à la grille des pixels d'une image. La matrice d'adjacence correspondante est une matrice très creuse avec au plus 4 valeurs non-nulles par ligne. La matrice est très structurée, je me demandais donc s'il existait une façon rapide de calculer les vecteurs propre est valeurs propres de cette matrice.

[davcha]

L'algorithme de Lanczos, je dirais.

[Alexis.M]

En fait je cherchais plutôt une solution analytique et elle existe.

Le graphe G du problème en 2D est factorisable en deux graphes 1-D Gx et Gy, qui sont simplement les graphes correspondant à une ligne et une colonne.

Du coup le Laplacien du graphe G peut s'écrire comme la somme de Kronecker (notée ++ ici) des Laplaciens des graphes Gx et Gy.

L = Lx ++ Ly

En conséquence si ui et vj sont des vecteurs propres respectifs de Lx et Ly avec les valeurs propres associées ci et dj, alors vj xx ui est vecteur propre de L avec la valeur propre ci + dj, où 'xx' désigne le produit de Kronecker.

Chose intéressante les vecteurs propres de Lx et Ly sont simplements la base des coeficients de la transformée et cosinus discrète DCT II.