Efficient implementation of iterative polynomial matrix EVD algorithms exploiting structural redundancy and parallelisation

Research output: Contribution to journalArticle

Abstract

A number of algorithms are capable of iteratively calculating a polynomial matrix eigenvalue decomposition (PEVD), which is a generalisation of the EVD and will diagonalise a parahermitian polynomial matrix via paraunitary operations. While offering promising results in various broadband array processing applications, the PEVD has seen limited deployment in hardware due to the high computational complexity of these algorithms. Akin to low complexity divide-and-conquer (DaC) solutions to eigenproblems, this paper addresses a partially parallelisable DaC approach to the PEVD. A novel algorithm titled parallel-sequential matrix diagonalisation exhibits significantly reduced algorithmic complexity and run-time when compared with existing iterative PEVD methods. The DaC approach, which is shown to be suitable for multi-core implementation, can improve eigenvalue resolution at the expense of decomposition mean squared error, and offers a trade-off between the approximation order and accuracy of the resulting paraunitary matrices.
LanguageEnglish
JournalIEEE Transactions on Circuits and Systems I: Regular Papers
Early online date25 Sep 2019
DOIs
Publication statusE-pub ahead of print - 25 Sep 2019

Fingerprint

Redundancy
Polynomials
Decomposition
Array processing
Parallel algorithms
Computational complexity
Hardware

Keywords

  • parahermitian matrix
  • paraunitary matrix
  • polynomial matrix eigenvalue decomposition
  • parallel
  • algorithm

Cite this

@article{757001fc4c4b46148504478ecd15c2fa,
title = "Efficient implementation of iterative polynomial matrix EVD algorithms exploiting structural redundancy and parallelisation",
abstract = "A number of algorithms are capable of iteratively calculating a polynomial matrix eigenvalue decomposition (PEVD), which is a generalisation of the EVD and will diagonalise a parahermitian polynomial matrix via paraunitary operations. While offering promising results in various broadband array processing applications, the PEVD has seen limited deployment in hardware due to the high computational complexity of these algorithms. Akin to low complexity divide-and-conquer (DaC) solutions to eigenproblems, this paper addresses a partially parallelisable DaC approach to the PEVD. A novel algorithm titled parallel-sequential matrix diagonalisation exhibits significantly reduced algorithmic complexity and run-time when compared with existing iterative PEVD methods. The DaC approach, which is shown to be suitable for multi-core implementation, can improve eigenvalue resolution at the expense of decomposition mean squared error, and offers a trade-off between the approximation order and accuracy of the resulting paraunitary matrices.",
keywords = "parahermitian matrix, paraunitary matrix, polynomial matrix eigenvalue decomposition, parallel, algorithm",
author = "Coutts, {Fraser K.} and Proudler, {Ian K.} and Stephan Weiss",
note = "{\circledC} 2019 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.",
year = "2019",
month = "9",
day = "25",
doi = "10.1109/TCSI.2019.2937006",
language = "English",
journal = "IEEE Transactions on Circuits and Systems I: Regular Papers",
issn = "1549-8328",

}

TY - JOUR

T1 - Efficient implementation of iterative polynomial matrix EVD algorithms exploiting structural redundancy and parallelisation

AU - Coutts, Fraser K.

AU - Proudler, Ian K.

AU - Weiss, Stephan

N1 - © 2019 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.

PY - 2019/9/25

Y1 - 2019/9/25

N2 - A number of algorithms are capable of iteratively calculating a polynomial matrix eigenvalue decomposition (PEVD), which is a generalisation of the EVD and will diagonalise a parahermitian polynomial matrix via paraunitary operations. While offering promising results in various broadband array processing applications, the PEVD has seen limited deployment in hardware due to the high computational complexity of these algorithms. Akin to low complexity divide-and-conquer (DaC) solutions to eigenproblems, this paper addresses a partially parallelisable DaC approach to the PEVD. A novel algorithm titled parallel-sequential matrix diagonalisation exhibits significantly reduced algorithmic complexity and run-time when compared with existing iterative PEVD methods. The DaC approach, which is shown to be suitable for multi-core implementation, can improve eigenvalue resolution at the expense of decomposition mean squared error, and offers a trade-off between the approximation order and accuracy of the resulting paraunitary matrices.

AB - A number of algorithms are capable of iteratively calculating a polynomial matrix eigenvalue decomposition (PEVD), which is a generalisation of the EVD and will diagonalise a parahermitian polynomial matrix via paraunitary operations. While offering promising results in various broadband array processing applications, the PEVD has seen limited deployment in hardware due to the high computational complexity of these algorithms. Akin to low complexity divide-and-conquer (DaC) solutions to eigenproblems, this paper addresses a partially parallelisable DaC approach to the PEVD. A novel algorithm titled parallel-sequential matrix diagonalisation exhibits significantly reduced algorithmic complexity and run-time when compared with existing iterative PEVD methods. The DaC approach, which is shown to be suitable for multi-core implementation, can improve eigenvalue resolution at the expense of decomposition mean squared error, and offers a trade-off between the approximation order and accuracy of the resulting paraunitary matrices.

KW - parahermitian matrix

KW - paraunitary matrix

KW - polynomial matrix eigenvalue decomposition

KW - parallel

KW - algorithm

U2 - 10.1109/TCSI.2019.2937006

DO - 10.1109/TCSI.2019.2937006

M3 - Article

JO - IEEE Transactions on Circuits and Systems I: Regular Papers

T2 - IEEE Transactions on Circuits and Systems I: Regular Papers

JF - IEEE Transactions on Circuits and Systems I: Regular Papers

SN - 1549-8328

ER -