a. Generalites.
Une modelisation creuse de matrice est une representation qui stocke seulement les coefficients non nuls de celle-ci.
Ce qui donne pour avantages :- Un gain de place selon le taux de remplissage de la matrice,Pour inconvenient, nous aurons certainement une perte d'efficacite quant-a l'acces a la valeur d'un emplacement quelconque de la matrice.
- Une connaissance, partant d'un coefficient non nul donne, du prochain coefficient non nul selon la ligne et/ou la colonne de maniere tres efficace. Cela traduit un gain immediat dans les operations de calcul sur celle-ci.b. L'existant.
Alp proposait principalement 2 structures de donnees distinctes pour la manipulation de matrices creuses :- sparse2d,Problemes principaux :
- superlu.* Modeles ' proprietaires', ne garantissant pas de genericite.=> Dans le but d'une connection generique avec ToricResultant, j'ai decide d''abandonner' en partie la compatibilite avec le type sparse2d, mais en en fournissant un remplacant.
* Necessite absolue de regarder les sources de la bibliotheque pour connaitre le comportement de telle ou telle primitive pour pouvoir l'utiliser. Par exemple, certains accesseurs vont allouer la memoire, d'autre non,... Pas de garantie, de standard d'utilisation.
* Les deux modeles, de par leur structure specifique, ne presentent pas de constructeurs commun.NOTA : Sont tout de meme fournies dans le package les sources de sparse2d avec les modifications que j'y ai realisees.
c. L'alternative...
1. Interface
Un nouveau modele de matrices creuse a ete cree. Il est propose comme experience pour l'elaboration d'une matrice creuse. C'est juste une vision 'personnelle' (et partielle) de la solution du probleme d'equilibre entre genericite et efficacite pour Sparse2d.
Le resultat fourni propose 2 niveaux d'interface :Le moteur, appele Sparse2d.[Je parle a partir d'ici du moteur Sparse2d, l'autre classe ne representant en fait que des reecritures d'appel pour Alp]Constructeurs :L'interface avec alp, appelee Sparse2dContainer, qui derive de maniere privee du moteur.Sparse2d(int NumberOfRows=0,int NumberOfColumns=0)Acces En Lecture :Mat[I][J]Acces En Ecriture :Mat[I][J]Constructeurs :Sparse2dContainer(int NbRows,int NbCols,int SorryWeDontCare=0)Acces En Lecture:Mat(i,j)Acces En Ecriture:Mat(i,j)
Pour avoir un accesseur de meme type que array2d, se rapprocher du mode d'utilisation des matrices denses.Mat(i,j,Val)
Pour tendre vers l'utilisation de superlu-tendre seulement, car pour superLU, cet accesseur suppose la matrice 'remplie',puisqu'elle realloue systematiquement les espaces memoires.Mat.Push(Val,i,j)
J'ai rajoute un accesseur Push a superlu et l'ancien sparse2d garantissant un meme comportement. Je le fournis donc aussi pour le nouveau type.Caracteristiques d'interface :
* Un seul constructeur tout ce qu'il y a de plus clair(Nb Lignes,Nb Colonnes).
* Gestion completement dynamique de la memoire => Comportement transparent.
* Non-proliferation d'accesseurs/constructeurs => 'Garanties' de comportement.2. Structure
Generalites :
La classe Sparse2d est toute en 'inline'. Tout le travail se fait dans ce dont elle derive publiquement :Sparse1d< Sparse1d < Type> > .On peut tres facilement la transformer enArray1d< Sparse1d < Type> >
voir dans le .H maniere + commentaires + implications.Caracteristiques de Sparse1d :
- Recherche de l'element par dychotomie.- Quand bien meme la memoire est dynamiquement alloue, on ne copie qu'une fois et une seule la donnee manipulee. Cet avantage est aussi un inconvenient : Il applique le meme traitement pour des objets que pour des types simples. Et pour ces derniers, il est clair que des solution simples sont plus rapides...
- L'acces en ecriture se fait par le biais d'un buffer. Ainsi, on n'alloue pas une case memoire pour l'utilisation de l'accesseur
en ecriture 'non judicieuse' ( rappelons que le compilateur choisit quel accesseur il va appeler seulement en fonction du type dont la reference est declaree).- Aucune garantie de compatibilite avec Alp. L'ecriture a ete clairement orientee dans l'optique de satisfaire aux besoins de Sparse2d.
3. Problemes en suspens
* PAS DE CONSTRUCTEUR DE COPIE. A faire pour Sparse1d et pour le modele de pile dont il a besoin.
* Accesseurs permettant d'exploiter la connaissance decoulant de la structure creuse non construite. Encore moins les operations de calcul allant avec. Remarque : Ils sont faciles a rajouter.
a. A l'origine
La fonction ToricResultant renvoyait un type fixe a l'avance : une matrice dense de doubles.
Et donc ne renvoyait de resultat que pour un certain type de systemes : n equations a n-1 inconnues.b. Maintenant
Le choix est laisse a l'utilisateur sous quelle forme il souhaite son resultat - dans la limite ou ce choix est compatible avec le systeme en entree.
On peut essayer :MatDense<array2d<X> >avec X pouvant etre :
MatSparse<Sparse2dContainer<X> >
MatSparse<superlu<Y> >double (systemes n equations, n-1 inconnues)Y ne pouvant etre que double. On ne peut demander le type superlu que dans le cadre de systemes n equations, n-1 inconnues).
UPoly (systemes n equations, n-1 ou n inconnues)
MPoly (systemes n equations, nombre d'inconnues >= n-1)
Voir Remarques.2.Alp.txt contenu dans le zip d'installation. Il contient en fait la liste des petits details que j'ai eu a rencontrer lors de la realisation du travail demande.
1. Telechargez et decompressez AlpAddOn.tgz quelque part,
2. Lancez :Setup [AlpDirectory]3. Suivez les instructions.un script de copie des fichiers que j'ai eu a modifier (il copie de toute la hierarchie se trouvant dans AlpAddOn/Alp/ -> [AlpDirectory]).instructions qui vous diront simplement de recompiler les librairies C du resultant et du volume mixte stable, et de mettre les archives dans lib-*.