Cyclic-by-row approximation of iterative polynomial EVD algorithms

Jamie Corr, Keith Thompson, Stephan Weiss, John G. McWhirter, Ian K. Proudler

Research output: Chapter in Book/Report/Conference proceedingChapter (peer-reviewed)

3 Citations (Scopus)

Abstract

A recent class of sequential matrix diagonalisation (SMD) algorithms have been demonstrated to provide a fast converging solution to iteratively approximating the polynomial eigenvalue decomposition of a parahermitian matrix. However, the calculation of an EVD, and the application of a full unitary matrix to every time lag of the parahermitian matrix in the SMD algorithm results in a high numerical cost. In this paper, we replace the EVD with a limited number of Givens rotations forming a cyclic-by-row Jacobi sweep. Simulations indicate that a considerable reduction in computational complexity compared to SMD can be achieved with a negligible sacrifice in diagonalisation performance, such that the benefits in applying the SMD are maintained.
LanguageEnglish
Title of host publicationSensor Signal Processing for Defence (SSPD), 2014
PublisherIEEE
Pages1-5
Number of pages5
ISBN (Print)978-1-4799-5294-6
DOIs
Publication statusPublished - Sep 2014
Event2014 Sensor Signal Processing for Defence - Scotland, Edinburgh, United Kingdom
Duration: 8 Sep 20149 Sep 2014

Conference

Conference2014 Sensor Signal Processing for Defence
CountryUnited Kingdom
CityEdinburgh
Period8/09/149/09/14

Fingerprint

Polynomials
Computational complexity
Decomposition
Costs

Keywords

  • computational complexity reduction
  • Jacobi sweep
  • sequential matrix diagonalisation algorithms
  • eigenvalues and eigenfunctions
  • iterative methods
  • signal processing

Cite this

Corr, J., Thompson, K., Weiss, S., McWhirter, J. G., & Proudler, I. K. (2014). Cyclic-by-row approximation of iterative polynomial EVD algorithms. In Sensor Signal Processing for Defence (SSPD), 2014 (pp. 1-5). IEEE. https://doi.org/10.1109/SSPD.2014.6943330
Corr, Jamie ; Thompson, Keith ; Weiss, Stephan ; McWhirter, John G. ; Proudler, Ian K. / Cyclic-by-row approximation of iterative polynomial EVD algorithms. Sensor Signal Processing for Defence (SSPD), 2014. IEEE, 2014. pp. 1-5
@inbook{0c836cd6e7b5432186118afb8ba95e62,
title = "Cyclic-by-row approximation of iterative polynomial EVD algorithms",
abstract = "A recent class of sequential matrix diagonalisation (SMD) algorithms have been demonstrated to provide a fast converging solution to iteratively approximating the polynomial eigenvalue decomposition of a parahermitian matrix. However, the calculation of an EVD, and the application of a full unitary matrix to every time lag of the parahermitian matrix in the SMD algorithm results in a high numerical cost. In this paper, we replace the EVD with a limited number of Givens rotations forming a cyclic-by-row Jacobi sweep. Simulations indicate that a considerable reduction in computational complexity compared to SMD can be achieved with a negligible sacrifice in diagonalisation performance, such that the benefits in applying the SMD are maintained.",
keywords = "computational complexity reduction, Jacobi sweep, sequential matrix diagonalisation algorithms, eigenvalues and eigenfunctions, iterative methods, signal processing",
author = "Jamie Corr and Keith Thompson and Stephan Weiss and McWhirter, {John G.} and Proudler, {Ian K.}",
year = "2014",
month = "9",
doi = "10.1109/SSPD.2014.6943330",
language = "English",
isbn = "978-1-4799-5294-6",
pages = "1--5",
booktitle = "Sensor Signal Processing for Defence (SSPD), 2014",
publisher = "IEEE",

}

Corr, J, Thompson, K, Weiss, S, McWhirter, JG & Proudler, IK 2014, Cyclic-by-row approximation of iterative polynomial EVD algorithms. in Sensor Signal Processing for Defence (SSPD), 2014. IEEE, pp. 1-5, 2014 Sensor Signal Processing for Defence, Edinburgh, United Kingdom, 8/09/14. https://doi.org/10.1109/SSPD.2014.6943330

Cyclic-by-row approximation of iterative polynomial EVD algorithms. / Corr, Jamie; Thompson, Keith; Weiss, Stephan; McWhirter, John G. ; Proudler, Ian K.

Sensor Signal Processing for Defence (SSPD), 2014. IEEE, 2014. p. 1-5.

Research output: Chapter in Book/Report/Conference proceedingChapter (peer-reviewed)

TY - CHAP

T1 - Cyclic-by-row approximation of iterative polynomial EVD algorithms

AU - Corr, Jamie

AU - Thompson, Keith

AU - Weiss, Stephan

AU - McWhirter, John G.

AU - Proudler, Ian K.

PY - 2014/9

Y1 - 2014/9

N2 - A recent class of sequential matrix diagonalisation (SMD) algorithms have been demonstrated to provide a fast converging solution to iteratively approximating the polynomial eigenvalue decomposition of a parahermitian matrix. However, the calculation of an EVD, and the application of a full unitary matrix to every time lag of the parahermitian matrix in the SMD algorithm results in a high numerical cost. In this paper, we replace the EVD with a limited number of Givens rotations forming a cyclic-by-row Jacobi sweep. Simulations indicate that a considerable reduction in computational complexity compared to SMD can be achieved with a negligible sacrifice in diagonalisation performance, such that the benefits in applying the SMD are maintained.

AB - A recent class of sequential matrix diagonalisation (SMD) algorithms have been demonstrated to provide a fast converging solution to iteratively approximating the polynomial eigenvalue decomposition of a parahermitian matrix. However, the calculation of an EVD, and the application of a full unitary matrix to every time lag of the parahermitian matrix in the SMD algorithm results in a high numerical cost. In this paper, we replace the EVD with a limited number of Givens rotations forming a cyclic-by-row Jacobi sweep. Simulations indicate that a considerable reduction in computational complexity compared to SMD can be achieved with a negligible sacrifice in diagonalisation performance, such that the benefits in applying the SMD are maintained.

KW - computational complexity reduction

KW - Jacobi sweep

KW - sequential matrix diagonalisation algorithms

KW - eigenvalues and eigenfunctions

KW - iterative methods

KW - signal processing

UR - http://ieeexplore.ieee.org/xpl/articleDetails.jsp?tp=&arnumber=6943330&queryText%3DCyclic-by-Row+Approximation+of+Polynomial+EVD+Algorithms

U2 - 10.1109/SSPD.2014.6943330

DO - 10.1109/SSPD.2014.6943330

M3 - Chapter (peer-reviewed)

SN - 978-1-4799-5294-6

SP - 1

EP - 5

BT - Sensor Signal Processing for Defence (SSPD), 2014

PB - IEEE

ER -

Corr J, Thompson K, Weiss S, McWhirter JG, Proudler IK. Cyclic-by-row approximation of iterative polynomial EVD algorithms. In Sensor Signal Processing for Defence (SSPD), 2014. IEEE. 2014. p. 1-5 https://doi.org/10.1109/SSPD.2014.6943330