Some fast algorithms multiplying a matrix by its adjoint. (March 2023)

• Record Type: Journal Article
• Authors: Dumas, Jean-Guillaume; Pernet, Clément; Sedoglavic, Alexandre
• Is Part Of: Journal of symbolic computation. Volume 115(2023)
• Page Start: 285
• Page End: 315
• Publication Date: 2023-03
• Subjects: Matrix multiplication -- Adjoint -- Quaternions -- Anti-homomorphism -- Skew-unitary matrix; Mathematics -- Data processing -- Periodicals; Numerical analysis -- Data processing -- Periodicals; Automatic programming (Computer science) -- Periodicals; Mathématiques -- Informatique -- Périodiques; Analyse numérique -- Informatique -- Périodiques; Programmation automatique -- Périodiques; Automatic programming (Computer science); Mathematics -- Data processing; Numerical analysis -- Data processing; Periodicals; Electronic journals; 510.285
• DOI: 10.1016/j.jsc.2022.08.009
• Languages: English
• ISSNs: 0747-7171

Abstract

Abstract: We present a non-commutative algorithm for the multiplication of a 2 × 2 block-matrix by its adjoint, defined by a matrix ring anti-homomorphism. This algorithm uses 5 block products (3 recursive calls and 2 general products). It works unconditionally in positive characteristic, or over the complex field with transposition, but for instance not over the complex field with conjugate-transpose. The resulting algorithm for arbitrary dimensions is a reduction of multiplication of a matrix by its adjoint to general matrix product, improving by a constant factor previously known reductions. We prove also that there is no algorithm derived from bilinear forms using only four products and the adjoint of one of them. Second we give novel dedicated algorithms for the complex field and the quaternions to compute the multiplication alternatively, taking advantage of the structure of the involved matrix-polynomial arithmetic. We then analyze the respective ranges of predominance of the two strategies. Finally we propose schedules with low memory footprint that support a fast and memory efficient practical implementation over a prime field.