Enquête sur les algorithmes / complexité de l'algèbre linéaire

20

Je recherche une bonne enquête sur les algorithmes et la complexité de l'algèbre linéaire (opérations comme le rang, l'inverse, les valeurs propres, ... pour les matrices booléennes, et entières / rationnelles) en mettant l'accent sur les algorithmes parallèles ( hiérarchie N C ) et polytemporels . Je n'ai pas pu en trouver un récent.FpNC

Connaissez-vous une bonne enquête récente ou un livre sur la complexité de l'algèbre linéaire?

Kaveh
la source

Réponses:

17

Deux références qui pourraient vous être utiles:

D. Bini et V. Pan. Calculs polynomiaux et matriciels, Volume 1: Algorithmes fondamentaux. Progrès en informatique théorique, Birkhauser, 1994.

J. von zur Gathen. Algèbre linéaire parallèle. Dans J. Reif, éditeur, Synthesis of Parallel Algorithms, chapitre 13. Morgan Kaufmann Publishers, Inc., 1993.

Ils ne sont pas nécessairement récents, mais ils constituent un bon point de départ.

John Watrous
la source
9

Que diriez-vous de la complexité des limites inférieures en utilisant l'algèbre linéaire ? Le livre n'est pas exactement ce que vous voulez, car il examine les limites inférieures à l' aide de l'algèbre linéaire, pas la complexité des problèmes d'algèbre linéaire. Pourtant, je pense que cela est utile de toute façon, car il est d'abord nécessaire de saisir la complexité des problèmes d'algèbre linéaire, puis de l'utiliser pour prouver les limites inférieures d'autres problèmes.

Voici la description du livre:

Alors que des progrès rapides ont été réalisés sur les bornes supérieures (algorithmes), les progrès sur les bornes inférieures sur la complexité des problèmes explicites sont restés lents malgré d'intenses efforts sur plusieurs décennies. Comme cela est naturel avec les résultats d'impossibilité typiques, les questions de limite inférieure sont des problèmes mathématiques difficiles et sont donc peu susceptibles d'être résolues par des attaques ad hoc. Au lieu de cela, des techniques basées sur des notions mathématiques qui capturent la complexité de calcul sont nécessaires. La complexité des limites inférieures à l'aide de l'algèbre linéaire étudie plusieurs techniques pour prouver les limites inférieures de la complexité booléenne, algébrique et de la communication en se basant sur certaines approches algébriques linéaires. Le thème commun à ces approches est d'étudier les mesures de robustesse du rang matricielqui capturent la complexité dans un modèle donné. Des limites inférieures convenablement fortes sur de telles fonctions de robustesse de matrices explicites entraînent des conséquences importantes dans les modèles de circuits ou de communication correspondants. Comprendre la complexité informatique inhérente des problèmes est d'une importance fondamentale en mathématiques et en informatique théorique. La complexité des limites inférieures à l'aide de l'algèbre linéaire est une référence inestimable pour toute personne travaillant dans le domaine.

PS: Vous avez demandé un livre, mais je crois que cet article: La complexité computationnelle de certains problèmes d'algèbre linéaire est également utile (mais il remonte à 1999).

MS Dousti
la source
Merci Sadeq. En fait, j'ai demandé un sondage ou un livre . Je vais jeter un œil à l'article bien qu'il ne semble pas être ce que je recherche.
Kaveh
Btw, j'ai le livre de Lokam et il est vraiment sympa.
Kaveh
7

Ce livre ne mentionne pas explicitement les algorithmes parallèles, mais le livre de Yap "Les problèmes fondamentaux de l'algèbre algorithmique" est une très bonne référence et discute de la complexité de nombreuses questions d'algèbre linéaire. Il y a un chapitre spécifiquement sur les systèmes linéaires traitant de la complexité temps / bit du calcul des déterminants, de l'inversion de matrice, des algorithmes de forme normale Hermite, entre autres.

Le livre traite également de la complexité de la multiplication, des bases de Grobner et des techniques de réduction du réseau (telles que LLL). Je ne le recommanderai jamais assez et je parie que vous y trouverez quelque chose de valable.

user834
la source