A Kogbetliantz-type algorithm for the hyperbolic SVD

DOI10.1007/S11075-021-01197-4zbMATH Open1492.65091arXiv2003.06701OpenAlexW3200667788WikidataQ115602962 ScholiaQ115602962MaRDI QIDQ2138394FDOQ2138394

Authors: Vedran Novaković, Sanja Singer 

Publication date: 11 May 2022

Published in: Numerical Algorithms (Search for Journal in Brave)

Abstract: In this paper a two-sided, parallel Kogbetliantz-type algorithm for the hyperbolic singular value decomposition (HSVD) of real and complex square matrices is developed, with a single assumption that the input matrix, of order $n$, admits such a decomposition into the product of a unitary, a non-negative diagonal, and a $J$-unitary matrix, where $J$ is a given diagonal matrix of positive and negative signs. When $J=pmI$, the proposed algorithm computes the ordinary SVD. The paper's most important contribution -- a derivation of formulas for the HSVD of $2imes2$ matrices -- is presented first, followed by the details of their implementation in floating-point arithmetic. Next, the effects of the hyperbolic transformations on the columns of the iteration matrix are discussed. These effects then guide a redesign of the dynamic pivot ordering, being already a well-established pivot strategy for the ordinary Kogbetliantz algorithm, for the general, $nimesn$ HSVD. A heuristic but sound convergence criterion is then proposed, which contributes to high accuracy demonstrated in the numerical testing results. Such a $J$-Kogbetliantz algorithm as presented here is intrinsically slow, but is nevertheless usable for matrices of small orders.

Full work available at URL: https://arxiv.org/abs/2003.06701

Recommendations

• Two-sided hyperbolic SVD
• A note on the hyperbolic singular value decomposition without hyperexchange matrices
• scientific article; zbMATH DE number 16399
• Computing the Generalized Singular Value Decomposition
• On efficient implementations of Kogbetliantz's algorithm for computing the singular value decomposition

zbMATH Keywords

Hermitian eigenproblemhyperbolic singular value decompositionKogbetliantz algorithmOpenMP multicore parallelization

Mathematics Subject Classification ID

Parallel numerical computation (65Y05) Eigenvalues, singular values, and eigenvectors (15A18) Numerical computation of eigenvalues and eigenvectors of matrices (65F15)

Cites Work

• LAPACK Users' Guide
• Structured Factorizations in Scalar Product Spaces
• A Jacobi eigenreduction algorithm for definite matrix pairs
• Block-oriented \(J\)-Jacobi methods for Hermitian matrices
• Componentwise analysis of direct factorization of real symmetric and Hermitian matrices
• A note on the existence of the hyperbolic singular value decomposition
• Existence of the hyperbolic singular value decomposition
• Indefinite QR factorization
• Title not available (Why is that?)
• Three-level parallel J-Jacobi algorithms for Hermitian matrices
• Dynamic ordering for a parallel block-Jacobi SVD algorithm
• Accuracy of two SVD algorithms for \(2\times 2\) triangular matrices
• On efficient implementations of Kogbetliantz's algorithm for computing the singular value decomposition
• Full block \(J\)-Jacobi method for Hermitian matrices
• Solution of linear equations by diagonalization of coefficients matrix
• On Jacobi Methods for Singular Value Decompositions
• On high relative accuracy of the Kogbetliantz method
• Parallelizing the Kogbetliantz method: a first attempt
• Accuracy of the Kogbetliantz method for scaled diagonally dominant triangular matrices
• Implementation of Jacobi Rotations for Accurate Singular Value Computation in Floating Point Arithmetic
• A GPU-based hyperbolic SVD algorithm
• Novel modifications of parallel Jacobi algorithms
• Optimal Sorting Algorithms for Parallel Computers
• Asymptotic quadratic convergence of the two-sided serial and parallel block-Jacobi SVD algorithm
• Hyperbolic-singular-value-decomposition-based square-root accurate continuous-discrete extended-unscented Kalman filters for estimating continuous-time stochastic models with discrete measurements
• The LAPW method with eigendecomposition based on the Hari-Zimmermann generalized hyperbolic SVD
• A Hierarchically Blocked Jacobi SVD Algorithm for Single and Multiple Graphics Processing Units
• Batched computation of the singular value decompositions of order two by the AVX-512 vectorization
• Hyperbolic SVD-based Kalman filtering for Chandrasekhar recursion

Cited In (4)

• Two-sided hyperbolic SVD
• Vectorization of a Thread-Parallel Jacobi Singular Value Decomposition Method
• A note on the hyperbolic singular value decomposition without hyperexchange matrices
• A GPU-based hyperbolic SVD algorithm

Uses Software

• LAPACK
• CUDA

This page was built for publication: A Kogbetliantz-type algorithm for the hyperbolic SVD

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2138394)