Module déterminant m

18

Quels sont les algorithmes efficaces connus pour calculer un déterminant d'une matrice entière à coefficients dans , l'anneau de résidus modulo . Le nombre peut ne pas être premier mais composite (donc les calculs sont effectués en anneau, pas dans un champ). mmZmmm

Pour autant que je sache (lire ci-dessous), la plupart des algorithmes sont des modifications de l'élimination gaussienne. La question porte sur l'efficacité de calcul de ces procédures.

S'il arrivait qu'il y ait une approche différente, je suis également curieux.

Merci d'avance.

Mise à jour:

Permettez-moi d'expliquer la source de cette question. Supposons que est un nombre premier. Donc est un champ. Et dans ce cas, nous pouvons effectuer tous les calculs en utilisant des nombres inférieurs à , nous avons donc une belle limite supérieure pour toutes les opérations sur les nombres: addition, multiplication et inversion --- toutes les opérations nécessaires pour exécuter l'élimination gaussienne.Z m mmZmm

En revanche, nous ne pouvons pas effectuer d'inversion pour certains nombres dans le cas où n'est pas un nombre premier. Nous avons donc besoin de quelques astuces pour calculer le déterminant.m

Et maintenant, je suis curieux de savoir quelles sont les astuces connues pour faire le travail et si de telles astuces peuvent être trouvées dans les papiers des livres.

Valeriy Sokolov
la source
3
Qu'entendez-vous par `` efficace ''? Le problème est clairement dans P .
david
2
est-il une constante fixe? Comment est-il administré? m
Michael Blondin
2
Qu'entendez-vous par petit? Pourraient-ils être écrits en unaire?
Michael Blondin
5
Je ne comprends toujours pas la question. Le déterminant d'une matrice entière peut être calculé en temps polynomial, vous pouvez donc simplement prendre cette valeur modulo . Pas besoin d'effectuer des divisions dans Z m ou de trouver la factorisation de m . mZmm
david
2
@ValeriySokolov: C'est l'algèbre linéaire de base. Par exemple, veuillez vérifier le problème 11.5.3 de complexité informatique de Christos H. Papadimitriou.
Tsuyoshi Ito

Réponses:

15

Si vous connaissez la factorisation de vous pouvez calculer modulo chaque p e i i séparément puis combiner les résultats en utilisant le reste chinois. Si e i = 1 , le calcul du modulo p e i i est facile, car il s'agit d'un champ. Pour les plus grands e i , vous pouvez utiliser le levage Hensel. m=p1e1pnenpieiei=1pieiei

Markus Bläser
la source
Je vous remercie! C'est comme quelque chose que je cherchais. Est-ce une pratique courante pour les déterminants? (les références sont les bienvenues).
Valeriy Sokolov
6
Ce sont des techniques standard de l'algèbre informatique. Jetez un œil à Modern Computer Algebra de von zur Gathen et Gerhard ou à tout autre livre sur l'algèbre informatique. Pour votre problème spécifique, voir également l'article suivant de Pan, Yu & Stewart comet.lehman.cuny.edu/vpan/pdf/pan146.pdf
Markus Bläser
17

Il existe un algorithme combinatoire de Mahajan et Vinay qui fonctionne sur des anneaux commutatifs: http://cjtcs.cs.uchicago.edu/articles/1997/5/contents.html

Sasho Nikolov
la source
Merci pour votre réponse avec lien vers un article très intéressant.
Valeriy Sokolov
Je pense également qu'il existe des algorithmes plus efficaces puisque les auteurs de cet article ont résolu un problème plus général (pour tout anneau commutatif).
Valeriy Sokolov
par "il y a" voulez-vous dire "connu" ou "existe" (mais n'a pas encore été trouvé)? c'est une supposition raisonnable, mais je suis un peu sceptique quant à la structure de l'anneau d'intigres modulo un petit nombre composite peut vous aider beaucoup. si je me trompe, je trouverais cela intéressant.
Sasho Nikolov
1
@ValeriySokolov pour être juste, puisque la réponse répond à votre question, vous pourriez envisager de l'accepter (ou si vous souhaitez attendre de meilleures réponses qui ne seraient pas déraisonnables)
Suresh Venkat
@SashoNikolov J'ai découvert que Wolfram Mathematica le calculait en quelque sorte. Dans les "Notes d'implémentation", ils disent: Det utilise des méthodes modulaires et la réduction des lignes, construisant un résultat en utilisant le théorème du reste chinois. J'aimerais savoir exactement ce qu'ils font, mais une recherche rapide ne m'a rien donné. Quant au "petit composite " cela signifie seulement que je veux considérer la complexité des additions et multiplications dans cet anneau comme étant O ( 1 ) . C'est que tous les facteurs comme O ( log m ) sont considérés comme O ( 1 ) . mO(1)O(logm)O(1)
Valeriy Sokolov
11

Pour résoudre ce problème, il existe un algorithme déterministe rapide basé sur les formes normales de Smith dont la complexité dans le pire des cas est limitée par le coût de la multiplication matricielle sur les entiers modulo . Pour toute matrice A , l'algorithme génère sa forme normale de Smith, d'où det ( A ) peut être facilement calculé.mAdet(A)

Plus concrètement, définissons sorte que deux n × n matrices avec des coefficients tirés de Z m puissent être multipliées en utilisant O ( n ω ) opérations arithmétiques de base sur Z m (addition entière, multiplication, exponentiation, etc.). Alors,ωn×nZmO(nω)Zm

Étant donné une matrice , il existe un algorithme déterministe qui calcule det ( A ) en utilisant O ( n ω ) des opérations arithmétiques de base sur Z m [1] .AZmn×ndet(A)O(nω)Zm

Quand cela a été écrit en 1996, il n'y avait pas d'alternative plus rapide asymptotiquement (l'article mentionne l'existence préalable d'algorithmes avec la même limite mais je ne sais pas lesquels, ni s'ils sont probabilistes).

Mise à jour (17 juillet 2013): une caractéristique intéressante de cet algorithme est qu'il s'exécute en temps polynomial pour un composite arbitraire sans connaître une factorisation en nombre premier de m ! C'est bien car il n'y a pas d'algorithmes efficaces (classiques) connus pour l'affacturage (bien sûr, si vous aviez un ordinateur quantique, alors vous pourriez appliquer l'algorithme de Shor ). Si vous n'avez la factorisation alors l'algorithme Markus suggéré semble plus simple à mettre en œuvre.mm

Notes: dans l'article, la complexité des "opérations arithmétiques de base" est O(log2m)O(M(logm)loglogm)M(t)tω

Juan Bermejo Vega
la source
θω
Peut-être, je ne connais pas la notation la plus courante pour cela.
Juan Bermejo Vega
Je pense que vous avez raison, je vais le changer pour qu'il soit "mainstream"
Juan Bermejo Vega