Performance trade-offs in sequential matrix diagonalisation search strategies

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

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

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.
LanguageEnglish
Title of host publication2015 IEEE 6th International Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP)
Place of PublicationPiscataway, NJ.
PublisherIEEE
Pages25-28
Number of pages4
ISBN (Print)9781479919635
DOIs
Publication statusPublished - 13 Dec 2015
Event6th IEEE Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP 2015) - Cancun, Mexico
Duration: 13 Dec 201516 Dec 2015

Workshop

Workshop6th IEEE Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP 2015)
CountryMexico
CityCancun
Period13/12/1516/12/15

Fingerprint

Energy transfer
Computational complexity
Polynomials
Decomposition
Costs
Experiments

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

Cite this

Corr, J., Thompson, K., Weiss, S., McWhirter, J. G., & Proudler, I. K. (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) (pp. 25-28). Piscataway, NJ.: IEEE. https://doi.org/10.1109/CAMSAP.2015.7383727
Corr, Jamie ; Thompson, Keith ; Weiss, Stephan ; McWhirter, John G. ; Proudler, Ian K. / Performance trade-offs in sequential matrix diagonalisation search strategies. 2015 IEEE 6th International Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP). Piscataway, NJ. : IEEE, 2015. pp. 25-28
@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 = "{\circledC} 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.",
year = "2015",
month = "12",
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; McWhirter, John G. ; Proudler, Ian K.

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 proceedingChapter (peer-reviewed)

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.

ER -

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