Inversion de matrice à coeff dans corps fini

Utilisation à l'épreuve de modélisation de l'agrégation de mathématiques

Modérateur : xcasadmin

Francky la Hache
Messages : 11
Inscription : lun. avr. 05, 2010 4:40 pm

Inversion de matrice à coeff dans corps fini

Message par Francky la Hache » sam. juil. 28, 2012 8:14 am

Bonjour,

je poste ici, sans être certain que ce soit le bon endroit, ...

Ma question n'est pas spécifique à l'utilisation de XCAS, mais c'est de l'algorithmique pas facile.
(J'utilise XCAS de temps en temps, mais je m'amuse surtout à coder en Python et C sur SPOJ, j'y ai fait quelques beaux coups ex1 ex2, ex3, ex4. )

Ma question est un conseil d'algorithme pour le problème suivant :
Quelques matrices n×n à coeff dans Fp sont données (2<=n,p<=100), déterminer leur inverse, si possible.

Parmi les pistes que j'envisage, lesquelles jugeriez vous raisonnable :
* méthode de pivot.
* déterminer le charpoly.
* tenter une exponentiation rapide pour certains exposants bien choisis (en rapport au cardinal du groupe linéaire)
* autre (?)

Bref, j'aimerais avoir une bonne piste pour me lancer dedans,
merci d'avance.
(Édit : le précalcul des inverses dans Fp*, prend moins de 3ko de données, que j'envisage d'inclure dans le code, il reste donc presque 20ko)

parisse
Messages : 4842
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: Inversion de matrice à coeff dans corps fini

Message par parisse » sam. juil. 28, 2012 11:22 am

Il y a 2 questions il me semble:
- la représentation choisie pour le corps Fp, si on a un cardinal petit le plus efficace c'est sans doute un entier avec une table pour les opérations de base
- le calcul de l'inverse d'une matrice: le pivot de Gauss convient très bien (O(n^3) opérations) et est surement mieux que les autres dont chaque étape est en O(n^3).

Francky la Hache
Messages : 11
Inscription : lun. avr. 05, 2010 4:40 pm

Re: Inversion de matrice à coeff dans corps fini

Message par Francky la Hache » sam. juil. 28, 2012 11:41 am

parisse a écrit :- la représentation choisie pour le corps Fp, si on a un cardinal petit le plus efficace c'est sans doute un entier avec une table pour les opérations de base
Merci pour cette réponse.

p est en effet petit. 2<= p <= 100.
Ce qui permet d'avoir de suite une table pour les inverses.
Je n'ai pas compris "la représentation choisie pour le corps Fp", quels sont les choix ?

L'idée serait d'avoir non seulement une table des inverses, mais mieux encore : table pour +, *, /,
c'est bien ça ?

--
Je vais commencer à implémenter le pivot.
Vous auriez quelques astuces sympa pour faire ça ?
n est au maximum 100, cela vaut-il le coup de faire des découpages par blocks ?
Je pensais déjà à :
1) stocker la matrice avec des lignes de longueurs puissance de 2, pour un accès plus rapide.
2) utiliser le type "unsigned char" pour stocker chaque coeff (donc moins de place), bonne idée ou pas trop ?
(le serveur de SPOJ est un vieux Pentium III, avec un cache plutôt réduit)
Merci encore.

Y a-t-il un lien vers un de vos cours concernant ce sujet ?
Ce serait tip top.

parisse
Messages : 4842
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: Inversion de matrice à coeff dans corps fini

Message par parisse » sam. juil. 28, 2012 4:20 pm

Francky la Hache a écrit : p est en effet petit. 2<= p <= 100.
Ce qui permet d'avoir de suite une table pour les inverses.
Je n'ai pas compris "la représentation choisie pour le corps Fp", quels sont les choix ?
A mon avis le mieux est une représentation additive, pour p=2 un bit par coeff de polynome, pour p=3 2 bits, pour p=5 et 7 3 bits. Ensuite ce sont des corps premiers si p^n<=100. L'addition et la soustraction se calculent par masques de bits et modulo (sauf pour p=2 ou c'est un ou exclusif). Pour le produit et l'inverse, on peut construire une table de correspondance entre représentation additive et puissances du générateur.
Je vais commencer à implémenter le pivot.
Vous auriez quelques astuces sympa pour faire ça ?
n est au maximum 100, cela vaut-il le coup de faire des découpages par blocks ?
Je pensais déjà à :
1) stocker la matrice avec des lignes de longueurs puissance de 2, pour un accès plus rapide.
2) utiliser le type "unsigned char" pour stocker chaque coeff (donc moins de place), bonne idée ou pas trop ?
(le serveur de SPOJ est un vieux Pentium III, avec un cache plutôt réduit)
Merci encore.

Y a-t-il un lien vers un de vos cours concernant ce sujet ?
Ce serait tip top.
Pour n<=100, inutile de faire compliqué, les trucs à la Strassen commencent à être intéressants plutot autour des 200 et plus (et c'est très lent en gain, au mieux 1/8 pour n*=2), et avec un unsigned char*100^2=10K, on reste en-dessous de la taille du cache.
Je n'ai pas vraiment de lien (et jamais implémenté de forme optimisée pour représenter les corps finis dans xcas), il y a un TP dans le cas p=2 là:
http://www-fourier.ujf-grenoble.fr/~parisse/#Crypto
Pour le pivot de Gauss, j'ai réussi très récemment à un peu optimiser le temps de calcul en "déroulant des boucles" et en faisant lu puis résolution de système, voir dans le source instable dans vecteur.cc doublerref (c'est pour des doubles à transposer donc).

Francky la Hache
Messages : 11
Inscription : lun. avr. 05, 2010 4:40 pm

Re: Inversion de matrice à coeff dans corps fini

Message par Francky la Hache » sam. juil. 28, 2012 6:15 pm

Merci pour ces pistes, je tiendrai au courant de l'aboutissement du truc.
Je suis content d'avoir la confirmation que Strassen est inutile ici...

Il y a déjà pas mal de boulot si on traite bien chaque type de cas.

--- (avec u8 pour unsigned char)
Pour la soustraction et la multiplication , j'avais pensé à écrire la table entière dans deux tableaux u8 *128*100.
Pour l'inverse, un simple u8 *100. (tous tiennent pre-calculé dans le source sans soucis, je recopie la tranche correspondant à p pour chaque matrice)
La matrice et son inverse en construction : u8 *256*100
Une ligne pour bricoler dessus : u8 *256
Ça fait 40ko environ pour l'ensemble (pire des cas), (ou je me trompe ?)
Pour la multiplication, si je fais cette table de correspondance avec le générateur, on gagne de la place (10ko), mais cela doit être plus coûteux en opérations, non ?
Je compte stocker mes tables à part ensuite, au cas où on tombe plusieurs fois sur le même premier p.

---
Dernier détail, je n'ai pas compris une remarque : "pour p^n<100 on a un corps premier".
Dans le problème p est premier entre 2 et 97,
qu'a-t-on de plus si p^n < 100 ?

parisse
Messages : 4842
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: Inversion de matrice à coeff dans corps fini

Message par parisse » dim. juil. 29, 2012 4:16 pm

40K, a mon avis ca donnera des performances moindres que si vous restez en-dessous des 32K. L'acces a la memoire est souvent l'element qui ralentit (et dans une moindre mesure les divisions en entier mais la il n'y en aura pas). Apres evidemment il ne faut pas avoir trop d'operations autres. Donc inutile a mon avis de faire des lignes de 256, mieux vaut des lignes de la taille (*2 si vous n'utilisez pas lu), et une table de passage de representation multiplicative en additive et reciproquement pour gagner 9.8K sur la multiplication.
Pour p>=11 si p^n<=100, alors n=1 et donc le corps est un Z/pZ, dans ce cas le mieux c'est sans doute de faire les operations arithmetiques + - * et un % p apres (et precalcul d'une table d'inverses).

Francky la Hache
Messages : 11
Inscription : lun. avr. 05, 2010 4:40 pm

Re: Inversion de matrice à coeff dans corps fini

Message par Francky la Hache » dim. juil. 29, 2012 5:56 pm

parisse a écrit :40K, a mon avis ca donnera des performances moindres que si vous restez en-dessous des 32K. L'acces a la memoire est souvent l'element qui ralentit (et dans une moindre mesure les divisions en entier mais la il n'y en aura pas). Apres evidemment il ne faut pas avoir trop d'operations autres. Donc inutile a mon avis de faire des lignes de 256, mieux vaut des lignes de la taille (*2 si vous n'utilisez pas lu), et une table de passage de representation multiplicative en additive et reciproquement pour gagner 9.8K sur la multiplication.
Pour p>=11 si p^n<=100, alors n=1 et donc le corps est un Z/pZ, dans ce cas le mieux c'est sans doute de faire les operations arithmetiques + - * et un % p apres (et precalcul d'une table d'inverses).
Ah, en fait je connaissais pas la tache du cache de la bécane de spoj. (Je croyais que 64ko passais)
Si n==1, alors la "matrice" est en effet triviale à inverser.

Merci.

parisse
Messages : 4842
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: Inversion de matrice à coeff dans corps fini

Message par parisse » dim. juil. 29, 2012 6:39 pm

je ne connais pas la taille du cache non plus, 32K c'est juste une valeur utilisee couramment, par exemple par msieve ou lapack.

Répondre