Lawra – linear algebra with recursive algorithms

Abstract

Recursion leads to automatic variable blocking for dense linear‐algebra algorithms. The recursive way of programming algorithms eliminates using BLAS level 2 during the factorization steps. For this and other reasons recursion usually speeds up the algorithms. The Cholesky factorization algorithm for positive definite matrices and LU factorization for general matrices are formulated. Different storage data formats and recursive BLAS are explained in this paper. Performance graphes of packed and recursive Cholesky algorithms are presented.

Lawra – rekursyviniai tiesinės algebros algoritmai

Santrauka. Rekursyviniai algoritmai leidžia automatiškai parinkti optimalų bloko dydį realizuojant tiesinės algebros algoritmus su pilnomis matricomis. Naudojant rekursyvinį programavimą išvengiama BLAS bibliotekos antrojo lygio paprogramių naudojimo vykdant faktorizacijos ciklą. Dėl šios ir kitų priežasčių rekursyviniai algoritmai dažniausiai yra greitesnį už standartinius tiesines algebros algoritmus. Straipsnyje pateikti Choleckio ir LU išskaidymo rekursyviniai algoritmai. Apibrėžti skirtingi rekursyviniai duomenų saugojimo formatai ir aprašytas naujas BLAS bibliotekos projektas. Pateikiami naujojo rekursyvinio Choleckio išskaidymo algoritmo efektyvumo tyrimo rezultatai, kurie buvo atlikti su įvairių tipų kompiuteriais.

First Published Online: 14 Oct 2010