377 KB20 KB197720261989Barle, JanezGrad, Janezletnik:13številka:4str. 38-43ISSN:0350-5596COBISSID:17649666URN:URN:NBN:SI:doc-WHB2N1F3enSlovensko društvo InformatikaInformatica (Ljubljana)hiperrazpršenostlinearno programiranjematematikamathematicsnumerična stabilnostoperacijsko raziskovanjeosebni računalnikprogramski paketirefaktorizacija bazne matrikeAssuring numerical stability in the process of matrix refactorization within linear programming package on PC|One of the most challenging tasks of those who develop linear programming software is development of quick, efficient and reliable matrix refactorization subroutine. The paper describes the implementation of this subroutine within the PC-LIP programming package, which we developed for the IBM-PC personal computers. A major design criterium for PC-LIP was to combine storage economy with numerical stability. The former was achieved using data structures which exploit super-sparsity and the latter implementing state of the art algorithms for basic matrix refactorization. These algorithms were combined with different tools satisfactory even on a badly scaled data which are quite common in practiceRazvoj hitrega, učinkovitega in zanesljivega podprograma za faktorizacijo bazne matrike spada med najbolj zahtevne naloge pri izgradnji programske opreme za linearno programiranje. Članek podaja opis implementacije tega podprograma v okviru programskega paketa PC-LIP, ki smo ga razvili za IBM kompatibilne osebne računalnike. Pri načrtovanju programskega paketa PC-LIP je bil glavni cilj vskladitev ekonomične izrabe pomnilnika z numerično stabilnostjo. To je bilo doseženo predvsem z uporabo podatkovnih struktur, ki izrabljajo hiperrazpršenost, in najbolj učinkovitih sodobnih algoritmov za izvajanje refaktorizacije bazne matrike. Ti algoritmi so bili kombinirani z različnimi postopki za zagotavljanje numerične stabilnosti. Razviti podprogram za refaktorizacijo je bil uspešen tudi na slabo pogojenih problemih, ki so v praksi dokaj pogostiTEXTznanstveno časopisjejournalsSlovenian National E-content AggregatorNational and University Library of SloveniaSlovensko društvo Informatika