ijle-matrixtechnieken. Behalve de coëfficiëntenmatrix van de correctievergelijkin
gen - die ook in SCAN al als ijle matrix werd behandeld en opgeslagen in een
datastructuur die bij ons bekend staat als 'zeefmatrix' - werd nu ook de
normaalmatrix zo behandeld. De programma's werden opgebouwd met behulp
van modulen, die zodanig werden gedefinieerd dat de probleemonafhankelijke
delen, bestaande uit onder andere het oplossen van de normaalvergelijkingen, de
toetsings- en betrouwbaarheidsberekeningen en de precisie, werden gescheiden
van de probleemafhankelijke. Hierdoor zouden belangrijke delen als
onafhankelijke modulen voor verschillende toepassingen kunnen worden ge
bruikt.
De opzet is geslaagd, want de programmatuur is door een aantal praktijkdiensten
in gebruik genomen: het Kadaster, Meetkundige Dienst Rijkswaterstaat en
Gasunie. Ook werden verschillende toepassingen gerealiseerd, onder andrere
vereffening van waterpasnetten, VLBI vereffeningen en fotogrammetrie.
Matrices en datastructuren
De genoemde zeefmatrices spelen dus een belangrijke rol in de software voor
vereffeningen. Hoewel het voor de hand ligt om in de programma's voor de
matrices twee-dimensionele arrays te gebruiken, is dit alleen voor matrices die
geheel of grotendeels met getallen ongelijk aan nul gevuld zijn een efficiënte
opslag. Zijn de matrices echter 'ijl', dat wil zeggen ze bevatten relatief veel
getallen gelijk aan nul, dan kan beter een daarvoor geschikte wijze van opslag
(datastructuur) worden gebruikt. Hiervoor zijn verschillende mogelijkheden
beschikbaar. Naast de bandmatrices en variabele bandmatrices voor symmetrische
matrices zoals de normaalmatrix, kan ook een algemene datastructuur worden
gebruikt die alleen niet-nul elementen bevat.
Een zeefmatrix is een dergelijke datastructuur: elk niet-nul element van de rijen
van een matrix wordt opgeslagen, tezamen met een verwijzing naar elke rij en het
kolomnummer van het opgeslagen element; alle nullen worden weggelaten.
Eenvoudig valt in te zien dat behalve de winst die in ruimte wordt gemaakt,
bewerkingen met dergelijke structuren (volgens de regels van de matrixrekening)
ook tot tijdwinst zullen leiden. Zo zal een matrixprodukt van twee ijle matrices
van orde O(n) een aantal scalaire produkten opleveren van 0(n als er met
twee-dimensionele arrays wordt gewerkt. Als van zeefmatrices gebruik gemaakt
wordt behoeven veel van deze produkten niet te worden uitgevoerd.
Alle matrices, ook de normaalmatrix, zijn in de meeste gevallen bij vereffeningen
van netwerken ijl tot zeer ijl. Hiervan kan dus in de software volop gebruik
worden gemaakt. De belangrijkste winst in SCAN-II ligt in het behandelen van
de normaalmatrix als ijle matrix en opslag als zeefmatrix. Als oplossingsmethode
85
