Les SIG font un usage intensif de matrices afin d’afficher leurs cartes ou transformer des coordonnées. On pourrait croire que le marché est suffisamment bien pourvu en excellentes bibliothèques de calculs matriciels, libres ou commerciales. Pourtant, les SIG ont des besoins spécifiques qui divergent un peu des objectifs de plusieurs bibliothèques existantes. Des manipulations de matrices comme celles décrites dans le chapitre sur les transformations affines interviennent dans quasiment toutes les opérations appliquées par Apache SIS sur des coordonnées. Mais l’analyse de ces opérations révèle quelques patterns:
Ces matrices sont presque toujours de petites tailles, dépassant rarement 5 lignes par 5 colonnes.
Les opérations matricielles « lourdes » (multiplications ou inversions de matrices) ne surviennent pas dans des endroits où la performance est importante. Dans la quasi-totalité des cas, elles ne sont effectuées qu’une fois pour toute, à la lecture d’un fichier, ou lors des étapes de préparation avant de convertir des coordonnées. Elles ne surviennent quasiment jamais dans la boucle convertissant chacune des coordonnées.
Dans une succession de multiplications et d’inversions de matrices, les erreurs d’arrondissement s’accumulent et grandissent rapidement au point de se confondre avec certaines opérations légitimes, notamment les changements de référentiel. Ces dernières s’expriment souvent par un changement de la taille, position et orientation de l’ellipsoïde choisi comme approximation de la forme de la Terre. Or ces changements de taille s’expriment en parties par million et les rotations en arc-secondes. Retranscrites dans une matrice, ces valeurs sont donc assez petites.
Il arrive fréquemment que des matrices s’annulent en tout ou en partie lorsqu’elles sont combinées, c’est-à-dire que leurs multiplications ramènent des facteurs d’échelles à 1 et des translations à 0. Toutefois les erreurs d’arrondissements font que les valeurs obtenues sont rarement exactes, mais plutôt des valeurs s’en rapprochant telles que 0,9999…97 à la place de 1. L’approche habituelle pour contourner ce problème est d’effectuer les comparaisons de nombres à virgule flottante en tolérant un léger écart. Mais il est difficile de choisir un seuil de tolérance qui gommera la plupart des erreurs d’arrondissement sans considérer à tord un changement de référentiel comme un artefact (voir point précédent).
Ces points font que, pour un SIG comme Apache SIS, la précision d’une bibliothèque de calculs matriciels est plus importante que la performance. Paradoxalement, un bon moyen de gagner en performance est justement d’investir davantage de temps de CPU pour effectuer des opérations matricielles plus précises dans la phase de préparation (non d’exécution) de la transformation de coordonnées, car on augmente ainsi les chances de détecter correctement quelles opérations s’annulent. L’effort investit dans cette détection permet de sauver du temps là où ça compte: quand viendra le moment de boucler sur des millions de coordonnées à transformer.
Mais les bibliothèques dédiées aux calculs matriciels sont souvent conçues pour opérer de manière très performante sur des matrices de grandes tailles, ayant par exemple des milliers de lignes et colonnes. Elles sont ainsi conçues pour être capable de résoudre efficacement des systèmes d’équations linéaires comportant des centaines d’inconnues. Les problèmes qu’elles résolvent sont certes difficiles, mais assez différents de ceux qui intéressent Apache SIS. Pour cette raison, et aussi à cause d’un autre besoin spécifique détaillé dans les paragraphes suivants, Apache SIS utilise ses propres fonctions de calculs matriciels. Ces fonctions tentent de résoudre le problème de précision en utilisant l’arithmétique « double-double » (une technique permettant de simuler une précision d’environ 120 bits) au prix de la performance pendant une étape (la préparation de la transformation) où elle n’est pas jugée critique.
Apache SIS a très souvent besoin d’inverser des matrices, afin d’obtenir une conversion de coordonnées dans la direction inverse de la conversion originale. Mais on n’inverse habituellement que des matrices carrées. Or, SIS a besoin d’effectuer des inversions de matrices non-carrées. Selon que l’on ait plus de lignes ou plus de colonnes:
Pour mieux comprendre les difficultés que causerait une transposition trop directe des bibliothèques d’algèbre linéaire aux SIG, imaginons une conversion (φ₁, λ₁, h) → (φ₂, λ₂) qui projetterait les points d’un espace 3D vers une surface 2D. Les termes φ sont des latitudes, λ des longitudes et (φ₂, λ₂) n’égale pas forcement (φ₁, λ₁) si la hauteur h n’est pas perpendiculaire à la surface.
Pour des bibliothèques d’algèbre linéaire, la matrice ci-dessus représente un système d’équations sous-déterminé, et donc insoluble. C’est-à-dire qu’on ne peut pas inverser cette conversion pour obtenir (φ₂, λ₂) → (φ₁, λ₁, h) puisqu’on ne sait pas quelle valeur donner à h, ce qui implique qu’on ne peut pas trouver (φ₁, λ₁) non-plus car ces valeurs dépendent peut-être de h. Toutefois dans le cas des SIG, l’axe des hauteurs ellipsoïdales h est perpendiculaire à la surface de l’ellipsoïde sur laquelle les latitudes et longitudes géodésiques (φ, λ) sont représentées (notez que cette affirmation ne s’applique pas aux latitudes et longitudes géocentriques). Cette perpendicularité rend φ₁ et λ₁ indépendants de h. Dans ce genre de cas, on peut encore sauver les meubles.
Apache SIS procède en vérifiant si les valeurs de h sont indépendantes des valeurs de φ et λ.
Nous reconnaissons ce cas en vérifiant quels coefficients de la matrice ont la valeur zéro.
Si SIS arrive à identifier des dimensions indépendantes,
il peut les exclure temporairement de manière à inverser sans ambiguïté la conversion dans les dimensions restantes.
S’il ne trouve pas de dimension indépendante, alors une exception est levée.
Mais si une inversion a été possible, alors il reste à décider du sort des dimensions que SIS avait temporairement exclues.
Par défaut, SIS assignera la valeur NaN (Not-a-Number) à ces dimensions.
Toutefois dans le cas particulier des hauteurs ellipsoïdales h dans une opération (φ₂, λ₂) → (φ₁, λ₁, h),
la valeur zéro peut aussi être appropriée dans l’hypothèse où les coordonnées sont habituellement proches de la surface de l’ellipsoïde.
Mais dans tous les cas, le choix du coefficient à mettre à 0 ou NaN est basé sur la présomption que la matrice représente une transformation affine.
Ce n’est pas une opération qui peut être effectuée sur des matrices arbitraires.
Le traitement particulier décrit ci-haut permet à Apache SIS de résoudre
certains systèmes d’équations sous-déterminés que l’on rencontre couramment dans les SIG.
Dans notre exemple utilisant NaN comme valeur par défaut, la coordonnée h reste inconnue
– nous ne faisons pas surgir de l’information du néant – mais au moins les coordonnées (φ, λ) ont pu être récupérées.
Le problème inverse, celui des systèmes surdéterminés, est plus subtil.
Une approche classique des bibliothèques d’algèbre linéaire est de résoudre les systèmes surdéterminés par la méthode des moindres carrées.
Transposée à notre exemple, cette approche proposerait une conversion (φ₂, λ₂, h) → (φ₁, λ₁)
qui semble le meilleur compromis pour diverses valeurs de φ₂, λ₂ et h,
tout en n’étant (sauf cas particuliers) une solution exacte pour personne.
De plus, les éventuelles combinaisons linéaires entre ces trois variables sont délicates compte tenu de l’hétérogénéité des unités de mesures,
avec par exemple les h en mètres et (φ, λ) en degrés.
Apache SIS procède plutôt comme pour les systèmes sous-déterminés: en exigeant que certaines dimensions soient indépendantes des autres,
faute de quoi la matrice sera considérée non-inversible.
En conséquence dans le cas des systèmes surdéterminés SIS refusera d’effectuer certaines opérations que les bibliothèques d’algèbre linéaire auraient faite,
mais en cas de succès les conversions obtenues seront garanties exactes (aux erreurs d’arrondissement prêts).
En résumé, les besoins qui ont amené Apache SIS à fournir ses propres fonctions de calculs matriciels sont:
Cette bibliothèque est fournie dans le paquet org.apache.sis.matrix du module sis-referencing.