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.

Rekursyviniai algoritmai leidžia automatiškai parinkti optimalu bloko dydi realizuojant tiesines algebros algoritmus su pilnomis matricomis. Naudojant rekursyvini programavima išvengiama BLAS bibliotekos antrojo lygio paprogramiu naudojimo vykdant faktorizaci‐jos cikla. Del šios ir kitu priežasčiu rekursyviniai algoritmai dažniausiai yra greitesni už standartinius tiesines algebros algoritmus. Straipsnyje pateikti Choleckio ir LU išskaidy‐mo rekursyviniai algoritmai. Apibrežti skirtingi rekursyviniai duomenu saugojimo formatai ir aprašytas naujas BLAS bibliotekos projektas. Pateikiami naujojo rekursyvinio Choleckio išskaidymo algoritmo efektyvumo tyrimo rezultatai, kurie buvo atlikti su ivairiu tipu kompiuteriais.