Performance trade-offs in sequential matrix diagonalisation search strategies

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

doi:10.1109/CAMSAP.2015.7383727

Performance trade-offs in sequential matrix diagonalisation search strategies

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

33 Downloads (Pure)

Abstract

Recently a selection of sequential matrix diagonalisation (SMD) algorithms have been introduced which approximate polynomial eigenvalue decomposition of parahermitian matrices. These variants differ only in the search methods that are used to bring energy onto the zero-lag. Here we analyse the search methods in terms of their computational complexities for different sizes of parahermitian matrices which are verified through simulated execution times. Another important factor for these search methods is their ability to transfer energy. Simulations show that the more computationally complex search methods transfer a greater proportion of the off-diagonal energy onto the zero-lag over a selected range of parahermitian matrix sizes. Despite their higher cost per iteration experiments indicate that the more complex search algorithms still converge faster in real time.

Original language	English
Title of host publication	2015 IEEE 6th International Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP)
Place of Publication	Piscataway, NJ.
Publisher	IEEE
Pages	25-28
Number of pages	4
ISBN (Print)	9781479919635
DOIs	https://doi.org/10.1109/CAMSAP.2015.7383727
Publication status	Published - 13 Dec 2015
Event	6th IEEE Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP 2015) - Cancun, Mexico Duration: 13 Dec 2015 → 16 Dec 2015

Workshop

Workshop	6th IEEE Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP 2015)
Country/Territory	Mexico
City	Cancun
Period	13/12/15 → 16/12/15

Keywords

Hermitian matrices
computational complexity
eigenvalues and eigenfunctions
matrix decomposition
polynomial approximation
search problems
algorithm design and analysis
approximation algorithms
complexity theory
covariance matrices
real-time systems
search methods

Access to Document

10.1109/CAMSAP.2015.7383727

Corr-etal-CAMSAP2015-Performance-trade-offs-in-sequential-matrix-diagonalisation-search-strategiesAccepted author manuscript, 125 KB

Cite this

@inbook{834a3e3f05e846b29de05d82bff0df7a,

title = "Performance trade-offs in sequential matrix diagonalisation search strategies",

abstract = "Recently a selection of sequential matrix diagonalisation (SMD) algorithms have been introduced which approximate polynomial eigenvalue decomposition of parahermitian matrices. These variants differ only in the search methods that are used to bring energy onto the zero-lag. Here we analyse the search methods in terms of their computational complexities for different sizes of parahermitian matrices which are verified through simulated execution times. Another important factor for these search methods is their ability to transfer energy. Simulations show that the more computationally complex search methods transfer a greater proportion of the off-diagonal energy onto the zero-lag over a selected range of parahermitian matrix sizes. Despite their higher cost per iteration experiments indicate that the more complex search algorithms still converge faster in real time.",

keywords = "Hermitian matrices, computational complexity, eigenvalues and eigenfunctions, matrix decomposition, polynomial approximation, search problems, algorithm design and analysis, approximation algorithms, complexity theory, covariance matrices, real-time systems, search methods",

author = "Jamie Corr and Keith Thompson and Stephan Weiss and McWhirter, {John G.} and Proudler, {Ian K.}",

note = "{\textcopyright} 2015 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.; 6th IEEE Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP 2015) ; Conference date: 13-12-2015 Through 16-12-2015",

year = "2015",

month = dec,

day = "13",

doi = "10.1109/CAMSAP.2015.7383727",

language = "English",

isbn = "9781479919635",

pages = "25--28",

booktitle = "2015 IEEE 6th International Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP)",

publisher = "IEEE",

}

Corr, J, Thompson, K, Weiss, S, McWhirter, JG & Proudler, IK 2015, Performance trade-offs in sequential matrix diagonalisation search strategies. in 2015 IEEE 6th International Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP). IEEE, Piscataway, NJ., pp. 25-28, 6th IEEE Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP 2015), Cancun, Mexico, 13/12/15. https://doi.org/10.1109/CAMSAP.2015.7383727

Performance trade-offs in sequential matrix diagonalisation search strategies. / Corr, Jamie; Thompson, Keith; Weiss, Stephan et al.

2015 IEEE 6th International Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP). Piscataway, NJ. : IEEE, 2015. p. 25-28.

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

TY - CHAP

T1 - Performance trade-offs in sequential matrix diagonalisation search strategies

AU - Corr, Jamie

AU - Thompson, Keith

AU - Weiss, Stephan

AU - McWhirter, John G.

AU - Proudler, Ian K.

N1 - © 2015 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 - 2015/12/13

Y1 - 2015/12/13

N2 - Recently a selection of sequential matrix diagonalisation (SMD) algorithms have been introduced which approximate polynomial eigenvalue decomposition of parahermitian matrices. These variants differ only in the search methods that are used to bring energy onto the zero-lag. Here we analyse the search methods in terms of their computational complexities for different sizes of parahermitian matrices which are verified through simulated execution times. Another important factor for these search methods is their ability to transfer energy. Simulations show that the more computationally complex search methods transfer a greater proportion of the off-diagonal energy onto the zero-lag over a selected range of parahermitian matrix sizes. Despite their higher cost per iteration experiments indicate that the more complex search algorithms still converge faster in real time.

AB - Recently a selection of sequential matrix diagonalisation (SMD) algorithms have been introduced which approximate polynomial eigenvalue decomposition of parahermitian matrices. These variants differ only in the search methods that are used to bring energy onto the zero-lag. Here we analyse the search methods in terms of their computational complexities for different sizes of parahermitian matrices which are verified through simulated execution times. Another important factor for these search methods is their ability to transfer energy. Simulations show that the more computationally complex search methods transfer a greater proportion of the off-diagonal energy onto the zero-lag over a selected range of parahermitian matrix sizes. Despite their higher cost per iteration experiments indicate that the more complex search algorithms still converge faster in real time.

KW - Hermitian matrices

KW - computational complexity

KW - eigenvalues and eigenfunctions

KW - matrix decomposition

KW - polynomial approximation

KW - search problems

KW - algorithm design and analysis

KW - approximation algorithms

KW - complexity theory

KW - covariance matrices

KW - real-time systems

KW - search methods

UR - http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=7377772

UR - http://inspire.rutgers.edu/camsap2015/

U2 - 10.1109/CAMSAP.2015.7383727

DO - 10.1109/CAMSAP.2015.7383727

M3 - Chapter (peer-reviewed)

SN - 9781479919635

SP - 25

EP - 28

BT - 2015 IEEE 6th International Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP)

PB - IEEE

CY - Piscataway, NJ.

T2 - 6th IEEE Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP 2015)

Y2 - 13 December 2015 through 16 December 2015

ER -

Performance trade-offs in sequential matrix diagonalisation search strategies

Abstract

Workshop

Keywords

Access to Document

Other files and links

Fingerprint

Signal Processing Solutions for the Networked Battlespace

Cite this

Performance trade-offs in sequential matrix diagonalisation search strategies

Abstract

Workshop

Keywords

Access to Document

Other files and links

Fingerprint

Projects

Signal Processing Solutions for the Networked Battlespace

Cite this