Cyclic-by-row approximation of iterative polynomial EVD algorithms

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

doi:10.1109/SSPD.2014.6943330

Cyclic-by-row approximation of iterative polynomial EVD algorithms

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

Electronic And Electrical Engineering

Research output: Chapter in Book/Report/Conference proceeding › Chapter (peer-reviewed) › peer-review

5 Citations (Scopus)

82 Downloads (Pure)

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.

Original language	English
Title of host publication	Sensor Signal Processing for Defence (SSPD), 2014
Publisher	IEEE
Pages	1-5
Number of pages	5
ISBN (Print)	978-1-4799-5294-6
DOIs	https://doi.org/10.1109/SSPD.2014.6943330
Publication status	Published - Sept 2014
Event	2014 Sensor Signal Processing for Defence - Scotland, Edinburgh, United Kingdom Duration: 8 Sept 2014 → 9 Sept 2014

Conference

Conference	2014 Sensor Signal Processing for Defence
Country/Territory	United Kingdom
City	Edinburgh
Period	8/09/14 → 9/09/14

Keywords

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

Access to Document

10.1109/SSPD.2014.6943330

Corr-etal-SSPD-2014-Cyclic-by-row-approximation-of-iterativeAccepted author manuscript, 161 KB

Cite this

@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 = sep,

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",

note = "2014 Sensor Signal Processing for Defence ; Conference date: 08-09-2014 Through 09-09-2014",

}

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

T2 - 2014 Sensor Signal Processing for Defence

Y2 - 8 September 2014 through 9 September 2014

ER -

Cyclic-by-row approximation of iterative polynomial EVD algorithms

Abstract

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Signal Processing Solutions for the Networked Battlespace

Sensor Dignal Processing for Defence (SSPD 2014)

Cite this

Cyclic-by-row approximation of iterative polynomial EVD algorithms

Abstract

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Projects

Signal Processing Solutions for the Networked Battlespace

Activities

Sensor Dignal Processing for Defence (SSPD 2014)

Cite this