Some fast algorithms multiplying a matrix by its adjoint

Dumas, Jean-Guillaume; Pernet, Clément; Sedoglavic, Alexandre

Type de document :

Article dans une revue scientifique: Article original

DOI :

10.1016/j.jsc.2022.08.009

Titre :

Some fast algorithms multiplying a matrix by its adjoint

Auteur(s) :

Dumas, Jean-Guillaume [Auteur]
Calcul Algébrique et Symbolique, Sécurité, Systèmes Complexes, Codes et Cryptologie [CASC]
Pernet, Clément [Auteur]
Calcul Algébrique et Symbolique, Sécurité, Systèmes Complexes, Codes et Cryptologie [CASC]
Sedoglavic, Alexandre [Auteur]

Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]

Titre de la revue :

Journal of Symbolic Computation

Pagination :

285-315

Éditeur :

Elsevier

Date de publication :

2023-03

ISSN :

0747-7171

Discipline(s) HAL :

Informatique [cs]/Calcul formel [cs.SC]

Résumé en anglais : [en]

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 ...
Lire la suite >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)over C or in positive characteristic. 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 alternatively compute the multiplication taking advantage of the structure of the matrix-polynomial arithmetic involved. 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.Lire moins >

Langue :

Anglais

Comité de lecture :

Oui

Audience :

Internationale

Vulgarisation :

Non

Collections :

Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189

Source :

Harvested from HAL

Fichiers

https://hal.archives-ouvertes.fr/hal-03095393/document
Accès libre
Accéder au document

http://arxiv.org/pdf/2101.01025
Accès libre
Accéder au document

https://hal.archives-ouvertes.fr/hal-03095393/document
Accès libre
Accéder au document

https://hal.archives-ouvertes.fr/hal-03095393/document
Accès libre
Accéder au document

document
Accès libre
Accéder au document

aat_adjoint.pdf
Accès libre
Accéder au document

2101.01025
Accès libre
Accéder au document

document
Accès libre
Accéder au document

aat_adjoint.pdf
Accès libre
Accéder au document

Some fast algorithms multiplying a matrix ... BibTeX CSV Excel RIS

Fichiers

Some fast algorithms multiplying a matrix ...

BibTeX

CSV

Excel

RIS