Quelle est la complexité spatiale du calcul des valeurs propres?

Je recherche un document d'enquête ou un livre couvrant les résultats sur la complexité spatiale des opérations d'algèbre linéaire courantes telles que le classement matriciel, le calcul des valeurs propres, etc. est plus facile de tracer les résultats temporels. J'apprécie toute référence en la matière.

Merci.

linear-algebra space-complexity gil
la source

Je suppose que la complexité est toujours au plus linéaire (par exemple

pour une matrice

). Êtes-vous intéressé par "l'espace total" ou par "l'espace de travail"?

O (n m)

$O(nm)$

n \times m

$n\times m$

Yuval Filmus

j'aurais dû mentionner que je suis intéressé par l'espace de travail.

gil

Je suis sûr que c'est

pour une matrice . La raison fondamentale est que je connais deux méthodes utiles pour les calculer et que les deux sont quadratiques dans l'espace. Le premier consiste à calculer le polynôme caractéristique (quadratique) et à trouver les racines. Deuxièmement, j'utilise des méthodes d'approximation qui nécessitent toutes de stocker une matrice modifiée (mais je ne peux pas m'étendre là-dessus, cela fait un moment que je n'ai pas étudié l'algèbre linéaire numérique).

O (n^{2})

$\mathcal O(n^2)$

n \times n

$n\times n$

Pour développer le point soulevé par @Yuval Filmus, la complexité de l'espace est assez sensible au modèle de calcul spécifique. En particulier, étant donné que la sortie est de taille linéaire, on pourrait jouer des tours en utilisant la bande de sortie comme espace de travail, sauf si le modèle spécifie clairement une bande de sortie en écriture seule. Pour éviter de tels problèmes, je serais tenté de reformuler comme des problèmes de décision (par exemple donné en entrée trois matrices, vérifier si la troisième est le produit des deux premières). Pourriez-vous préciser le modèle que vous aviez en tête? (De plus, je ne connais pas de livres sur la complexité de l'espace, et je n'ai trouvé aucune enquête utile non plus.)

András Salamon

en ce qui concerne @ AndrásSalamon, une version de décision qui est utile pour moi peut être: la kième valeur propre est-elle plus grande que q. pour k entier et q rationnel. Merci.

gil

Réponses:

Les versions décisionnelles de nombreux problèmes courants en algèbre linéaire sur les entiers (ou rationnels) sont dans la classe , voir l'article $\mathsf{DET}$

Gerhard Buntrock, Carsten Damm, Ulrich Hertrampf, Christoph Meinel: Structure et importance de la classe Logspace-MOD. Théorie des systèmes mathématiques 25 (3): 223-237 (1992)

est contenu dans . $\mathsf{DET}$ $\mathsf{DSPACE}(\log^2)$

Le calcul des valeurs propres est un peu plus délicat:

1) Dans , on peut calculer les coefficients du polynôme caractéristique. $\mathsf{DSPACE}(\log^2)$

2) Ensuite, vous pouvez utiliser l'algorithme parallèle de Reif et Neff pour calculer des approximations aux valeurs propres. L'algorithme s'exécute sur une CREW-PRAM en temps logarithmique avec de nombreux processeurs polynomiaux, il peut donc être simulé avec un espace poly-logarithmique. (Ce n'est pas explicitement indiqué dans l'article, mais leur PRAM doit être uniforme dans l'espace logarithmique.) L'espace utilisé est polylogarithmique dans la taille de la matrice d'entrée et la précision . La précision signifie que vous obtenez des approximations jusqu'à une erreur additive de . $p$ $p$ $2^{-p}$

Il s'agit d'une concaténation de fonctions calculables dans l'espace poly-logarithmique. (Les bandes de sortie sont en écriture seule et à sens unique.)

C. Andrew Neff, John H. Reif: Un algorithme efficace pour le problème des racines complexes. J. Complexity 12 (2): 81-115 (1996)

Markus Bläser
la source

$log^2$ $NC^2$

Lior Eldar
la source