Iterative and parallel methods for linear systems, with applications in circuit simulation

摘要

Bij het ontwerp van elektronische schakelingen, ie gebruikt wor en in bijvoorbeeld CD-spelersuden mobiele telefoons, maakt e ontwerper veelvul ig gebruik van circuitsimulatieudBij circuitsimulatie wor t het ge rag van een schakeling (circuit) oorgereken met eenudcomputer Hier oor wor t het maken van ure prototypes groten eels overbo ig Ookudzou zon er eze simulaties het ontwerpen van complexe ge¨integreer e schakelingen, metudvele uizen en transistoren, con ensatoren, weerstan en en ergelijke, niet mogelijkudzijn Om snel een circuit te kunnen ontwerpen is het voor e ontwerper van belang at eudsimulatie niet te veel (computer-)rekentij kost Met snellere (slimmere) rekenmetho enuden ook met snellere computers, kan e rekentij verkort wor enudDit proefschrift gaat groten eels over metho en ie tot oel hebben e rekentij voorudhet simuleren van een circuit korter te maken De nieuwe metho en ie we ontwikkeludhebben zou en echter ook nuttig kunnen zijn bij e simulatie van an ere verschijnselen,udzoals bijvoorbeel vloeistofstromingen en chemische processenudBij het simuleren van circuits wor t e meeste rekentij gebruikt voor het oplossenudvan grote stelsels lineaire algebra¨ische vergelijkingen Een stelsel van 2 vergelijkingenudmet 2 onbeken en, x en y, is bijvoorbeelududud3x +5y =14ud2x 3y =3,udmet als oplossing x =3eny = 1 Bij circuitsimulatie kunnen e stelsels zeer veel,udbijvoorbeel meer an 50000, vergelijkingen hebben en evenveel onbeken en Dezeudstelsels hebben an wel een ijle structuur Dat wil zeggen at er veel vergelijkingenudzijn ie slechts van een klein aantal onbeken en afhangen Door op een slimme manierudgebruik te maken van eze structuur kan er veel rekentij bespaar wor en Na hetudinlei en e eerste hoof stuk beschrijven we in e hoof stukken 2 en 3 een gecombineer eudirecte en iteratieve metho e voor het oplossen van eze stelsels vergelijkingenudBij een irecte metho e wor en onbeken en weggewerkt oor een geschikt veelvouudvan een vergelijking bij een an ere vergelijking op te tellen Op eze manier kan uitein-udelijk e oplossing van het grote stelsel uitgereken wor en Bij een iteratieve metho eudgebeurt ongeveer hetzelf e, maar e hoeveelhei rekenwerk wor t sterk beperkt oor opudgeschikte plaatsen in het proces co¨effici¨enten te verwaarlozen Het resultaat is an weludeen bena ering van e oplossing in plaats van e exacte oplossing Men tracht e foutudin e oplossing te verkleinen oor een correctie op e oplossing aan te brengen Dezeudcorrectie wor t gevon en oor een vergelijking voor e fout op te stellen en eze even-eensudbij bena ering op te lossen Dit wor t herhaal tot at een vol oen nauwkeurigeudoplossing gevonden is In e praktijk maken circuitsimulatie-programma s vooral gebruik van irecte metho-uden, om at eze sneller bleken te zijn an e tot nu toe bestaan e iteratieve metho enudIn hoof stuk 2 laten we zien at een gecombineer e irecte en iteratieve metho e weludrie keer sneller kan zijn an een irecte metho e Een prettige bijkomstighei van ezeudaanpak is at hij ook geschikt is voor parallelle computers Dat zijn computers waarinudtwee of meer processoren samenwerken Met eze computers kan het rekenwerk ver erudversnel wor en met een factor ie kan oplopen tot het aantal processorenudHoofdstuk 4 gaat over het oplossen van lineaire stelsels vergelijkingen die optredenudbij het simuleren van de periodieke stabiele toestan van een circuit Het gaat hierbij omudcircuits waarvan alle spannings- en stroombronnen periodiek zijn in de tijd. Dit heeftudtot gevolg dat alle spanningen en stromen in het circuit zich na een bepaalde periodeudherhalen Simulatie van deze circuits geeft lineaire stelsels met een cyclische structuurudBestaande methoden voor it soort stelsels zijn niet zo goed geschikt voor parallelleudcomputers De methode die we in hoofdstuk 4 voorstellen is dat wel De totale hoeveelheidudrekenwerk is bij deze methode iets groter dan bij de bestaande methoden, maar dankzij het parallellisme kunnen de stelsels vergelijkingen op een parallelle computerudtoch beduiden sneller worden opgelostudHoofdstuk 5 gaat over een iteratieve methode voor lineaire stelsels vergelijkingenudwaarbij de co¨effici¨entenmatrix een polynoom is van een andere matrix Dit type lineaireudstelsels komt onder andere voor bij een toepassing in de natuurkunde Er zijn (nog) geenudtoepassingen in circuitsimulatie Door de speciale structuur van het stelsel uit te buitenudverkrijgen we een effici¨ente methode De nieuwe methode geeft vaak iets nauwkeurigerudresultaten dan de bestaande methoden voor dit soort stelsels