Limites inférieures de la complexité gaussienne

18

Définissez la complexité gaussienne d'une matrice comme le nombre minimal d'opérations élémentaires de ligne et de colonne nécessaires pour amener la matrice sous une forme triangulaire supérieure. Il s'agit d'une quantité comprise entre 0 et n 2 (via élémination gaussienne). La notion prend tout son sens dans n'importe quel domaine.n×n0n2

Ce problème semble certainement très fondamental et il a dû être étudié. Étonnamment, je ne connais aucune référence. Je serai donc satisfait de toute référence. Mais, bien sûr, la question principale est:

Existe-t-il des limites inférieures explicites non triviales connues?

Par non trivial, je veux dire super-linéaire. Juste pour être clair: sur les champs finis, un argument de comptage montre qu'une matrice aléatoire a un ordre de complexité n ^ 2 (une affirmation similaire devrait être vraie sur des champs infinis). Par conséquent, ce que nous recherchons est une famille explicite de matrices, par exemple, les matrices de Hadmard. C'est la même chose qu'avec la complexité du circuit booléen où nous savons qu'une fonction aléatoire a une complexité élevée, mais nous recherchons des fonctions explicites avec cette propriété.

Moritz
la source
Je ne sais pas exactement quelle est la question ici. Demandez-vous des formes spécifiques de matrices, ou le cas général (auquel cas un simple argument de comptage semble fonctionner)?
Joe Fitzsimons
@Joe, comme mentionné, je demande une famille explicite de matrices, par exemple, les matrices Hadamard. Comme d'habitude, les matrices aléatoires trichent. C'est de la même manière que nous ne sommes pas satisfaits du fait qu'une fonction aléatoire nécessite de grands circuits. J'ai ajouté un paragraphe pour souligner ce point.
Moritz
peut-être que cela devrait être republié comme réponse :)
Suresh Venkat
Ok, je vais le faire.
Joe Fitzsimons
En fait, je crois que ma méthode peut avoir été défectueuse.
Joe Fitzsimons

Réponses:

17

Cela semble être un problème très difficile, lié à un problème plus largement étudié.

Supposons que nous considérons une matrice carrée inversible A et définissons c (A) comme le nombre minimal d'opérations de lignes élémentaires nécessaires pour réduire A à la matrice d'identité. Cette mesure de complexité est plus grande que celle suggérée par Moritz, donc prouver les limites super-linéaires ne peut être que plus facile.

Maintenant, les opérations de ligne sont réversibles . Il s'ensuit que c (A) peut être défini de manière équivalente comme le nombre minimum d'opérations de ligne nécessaires pour produire A, à partir de la matrice d'identité.

Notez que la production de A de cette manière donne lieu à un circuit arithmétique pour calculer la carte en prenant x à Ax. Le fanin de chaque porte est de 2 et le nombre de portes sans entrée correspond au nombre d'opérations de ligne.

Il n'y a pas de réduction évidente dans le sens inverse (des circuits aux séquences de lignes). Pourtant, nous pouvons caractériser c (A) en termes de complexité du circuit arithmétique d'Ax dans un modèle de circuit restreint: je prétends que c (A) est égal à la moitié du nombre minimum d'arêtes dans un circuit arithmétique pour A, de fanin au plus 2 et largeur n, où nous ne facturons pas les bords menant aux portes de fanin 1. (J'utilise ici la notion habituelle de largeur de circuit.) Cela peut être montré en utilisant l'idée simple esquissée précédemment.

Voici maintenant le lien avec des problèmes bien étudiés: c'est un problème ouvert célèbre depuis plus de 30 ans d'exposer une carte linéaire explicite Axe (sur n'importe quel champ fini) qui nécessite un nombre superlinéaire de portes dans un circuit fanin-2. La référence classique est Valiant, «Arguments théoriques des graphes dans une complexité de bas niveau», et une récente enquête FTTCS de Lokam est également utile.

En étudiant c (A), nous imposons une restriction de largeur supplémentaire, mais comme notre restriction est si faible (largeur n), je ne m'attends pas à ce que le problème devienne beaucoup plus facile. Mais bon - j'adorerais avoir tort.

Andy Drucker
la source
2
En outre, Gowers sur son blog a eu une discussion sur la complexité de l'élimination gaussienne. Je ne l'ai pas lu attentivement (c'est sous la forme d'un long dialogue), mais cela peut être utile: gowers.wordpress.com/2009/11/03/…
Andy Drucker
Juste pour comprendre cela correctement, la restriction de largeur vient parce que vous avez au plus n opérations par colonne, et vous pouvez procéder colonne par colonne?
Moritz
Je pense en termes d'opérations de ligne. La restriction de largeur n correspond au fait que nous avons n lignes avec lesquelles travailler dans lesquelles tout notre travail intermédiaire aurait lieu. Les n portes de circuit à la profondeur t représentent les états des n lignes après t applications des opérations de ligne. (peut-être que vous dites la même chose que moi)
Andy Drucker
Si nous autorisions à la place des lignes supplémentaires d '«espace de travail auxiliaire» dans notre élimination gaussienne, je pense que nous obtiendrions une correspondance exacte entre la complexité de la réduction de A à l'identité et la complexité du circuit arithmétique linéaire d'Ax (qui est essentiellement la complexité arithmétique ckt, car les multiplications ne permettent pas de calculer des fonctions linéaires au-delà d'un facteur constant).
Andy Drucker
Oui, c'est ce que je voulais dire. Je suis également d'accord avec la deuxième déclaration. Un circuit linéaire général peut en quelque sorte créer de nouvelles lignes quand il le veut :-)
Moritz
9

Il y a des références, et elles sont assez anciennes. Je les ai rencontrés en travaillant sur des algorithmes combinatoires pour la multiplication matricielle booléenne.

Θ(n2/logn)Journaln

JW Moon et L. Moser. Un problème de réduction de matrice. Mathématiques du calcul 20 (94): 328-330, 1966.

L'article devrait être accessible sur JSTOR.

Je suis à peu près sûr que la borne inférieure n'est qu'un argument de comptage, et aucune matrice explicite atteignant la borne inférieure n'a été donnée.

Ryan Williams
la source