Preconditioningtekniikat

Preconditioningtekniikat ovat menetelmiä, joilla suurten ja harvaverkkoisten lineaaristen järjestelmien Ax = b ratkaisemisen konvergenssia nopeutetaan. Niiden avulla järjestelmä muokataan siten, että Krylov-tyyppiset iteraattorit, kuten conjugate gradient (CG) tai GMRES, tarvitsevat vähemmän iteraatioita. Tämä toteutetaan käyttämällä esikäsittelijää M, jonka avulla ratkaistaan joko vasen esikäsitelty järjestelmä M^{-1}A x = M^{-1}b, oikea esikäsittely A M^{-1} y = b (x = M^{-1} y), tai kaksipuolinen M_L^{-1} A M_R^{-1} y = b. Esikäsittelijän tulee olla helposti laskettava ja sovellettavissa sekä tarjota parempi spektri kuin alkuperäinen A.

Yleisimmät esikäsittelijät ovat diagonaalinen (Jacobi) esikäsittely, epätarkat faktorisoinnit kuten ILU/IC ja niiden muunnelmat (esimerkiksi ILUT, ILUTP), sekä likimääräiset käänteiset esikäsittelijät (SPAI, AINV). Lisäksi monesti käytetään polynomipreconditioners kuten Chebyshev. Myös domain decomposition -lähestymistapoja (additive Schwarz, BDDC) sekä multigrid-tyyppisiä ratkaisuja hyödynnetään joko esikäsittelyinä tai niiden osina.

Valinta ja vaikutus riippuvat ongelmasta. Hyvä esikäsittelijä laskee M^{-1} nopeasti ja kustannustehokkaasti sekä muuttaa A:n spektrin siten, että iteraatiolukumäärä pienenee. Toisaalta liian kallis esikäsittely tai huonosti valittu M voi hidastaa ratkaisua. Siksi valinta perustuu ongelmakohtaisiin ominaisuuksiin, kuten matriisin sparsisuuteen, koon ja koeffisienttien vaihteluun.

Käytännössä preconditioning on keskeinen tekijä suurten epälineaaristen PDE-järjestelmien sekä muiden suurten, harvakerroksisten lineaaristen ongelmien ratkaisemisessa, joissa Krylov-tyyppiset menetelmät yhdistettynä sopivaan esikäsittelyyn saavuttavat kohtuulliset konvergenssiarvot.