Naslov
A block algorithm for computing antitriangular factorizations of symmetric matrices

Autori
Bujanović, Zvonimir ; Kressner, Daniel

Izvornik
Numerical algorithms (1017-1398) 71 (2016), 1; 41-57

Vrsta, podvrsta i kategorija rada
Radovi u časopisima, članak, znanstveni

Ključne riječi
Antitriangular factorization ; Matrix inertia ; Block algorithm ; Symmetric matrix

Sažetak
Any symmetric matrix can be reduced to antitriangular form in finitely many steps by orthogonal similarity transformations. This form reveals the inertia of the matrix and has found applications in, e.g., model predictive control and constraint preconditioning. Originally proposed by Mastronardi and Van Dooren, the existing algorithm for performing the reduction to antitriangular form is primarily based on Householder reflectors and Givens rotations. The poor memory access pattern of these operations implies that the performance of the algorithm is bound by the memory bandwidth. In this work, we develop a block algorithm that performs all operations almost entirely in terms of level 3 BLAS operations, which feature a more favorable memory access pattern and lead to better performance. These performance gains are confirmed by numerical experiments that cover a wide range of different inertia.

Izvorni jezik
Engleski

Znanstvena područja
Matematika

POVEZANOST RADA