Pentadiagonal Companion Matrices

Brydon Eastman; Kevin N. Vander Meulen

Special Matrices (2016)

  • Volume: 4, Issue: 1, page 13-30
  • ISSN: 2300-7451

Abstract

top
The class of sparse companion matrices was recently characterized in terms of unit Hessenberg matrices. We determine which sparse companion matrices have the lowest bandwidth, that is, we characterize which sparse companion matrices are permutationally similar to a pentadiagonal matrix and describe how to find the permutation involved. In the process, we determine which of the Fiedler companion matrices are permutationally similar to a pentadiagonal matrix. We also describe how to find a Fiedler factorization, up to transpose, given only its corner entries.

How to cite

top

Brydon Eastman, and Kevin N. Vander Meulen. "Pentadiagonal Companion Matrices." Special Matrices 4.1 (2016): 13-30. <http://eudml.org/doc/276929>.

@article{BrydonEastman2016,
abstract = {The class of sparse companion matrices was recently characterized in terms of unit Hessenberg matrices. We determine which sparse companion matrices have the lowest bandwidth, that is, we characterize which sparse companion matrices are permutationally similar to a pentadiagonal matrix and describe how to find the permutation involved. In the process, we determine which of the Fiedler companion matrices are permutationally similar to a pentadiagonal matrix. We also describe how to find a Fiedler factorization, up to transpose, given only its corner entries.},
author = {Brydon Eastman, Kevin N. Vander Meulen},
journal = {Special Matrices},
keywords = {companion matrices; pentadiagonal matrices; Fiedler companion matrices; Hessenberg matrices; algorithms; zeros of polynomials},
language = {eng},
number = {1},
pages = {13-30},
title = {Pentadiagonal Companion Matrices},
url = {http://eudml.org/doc/276929},
volume = {4},
year = {2016},
}

TY - JOUR
AU - Brydon Eastman
AU - Kevin N. Vander Meulen
TI - Pentadiagonal Companion Matrices
JO - Special Matrices
PY - 2016
VL - 4
IS - 1
SP - 13
EP - 30
AB - The class of sparse companion matrices was recently characterized in terms of unit Hessenberg matrices. We determine which sparse companion matrices have the lowest bandwidth, that is, we characterize which sparse companion matrices are permutationally similar to a pentadiagonal matrix and describe how to find the permutation involved. In the process, we determine which of the Fiedler companion matrices are permutationally similar to a pentadiagonal matrix. We also describe how to find a Fiedler factorization, up to transpose, given only its corner entries.
LA - eng
KW - companion matrices; pentadiagonal matrices; Fiedler companion matrices; Hessenberg matrices; algorithms; zeros of polynomials
UR - http://eudml.org/doc/276929
ER -

References

top
  1. [1] J.L. Aurentz, R. Vandebril, and D.S. Watkins, Fast computation of the zeros of a polynomial via factorization of the companion matrix, SIAM J. Sci. Comput.35 (2013) A255 – A269.[WoS] Zbl1264.65074
  2. [2] J.L. Aurentz, R. Vandebril, and D.S. Watkins, Fast computation of eigenvalues of companion, comrade, and related matrices, BIT Numer. Math.54 (2014) 7–30. Zbl1293.65052
  3. [3] T. Bella, V. Olshevsky, and P. Zhlobich, A quasiseparable approach to five-diagonal CMV and Fiedler matrices, Linear Algebra Appl.434(4) (2011) 957–976.[WoS] Zbl1215.15014
  4. [4] B. Bevilacqua, G.M. Del Corso, and L. Gemignani, A CMV–based eigensolver for companion matrices, SIAM J. Matrix Anal. Appl.36(3) (2015) 1046–1068.[WoS][Crossref] Zbl1321.65076
  5. [5] D.A. Bini, P. Boito, Y. Eidelman, L. Gemignani, and I. Gohberg, A fast implicit QR eigenvalue algorithm for companion matrices, Linear Algebra Appl.432(8) (2010) 2006–2031.[WoS] Zbl1188.65039
  6. [6] D.A. Bini, F. Daddi, and L. Gemignani, On the shifted QR iteration applied to companion matrices, Electron. Trans. Numer. Anal.18 (2004) 137–152. Zbl1066.65039
  7. [7] S. Chandrasekaran, M. Gu, J. Xia, and J. Zhu, A fast QR algorithm for companion matrices, Oper. Theory Adv. Appl.179 (2008) 111–143. Zbl1136.65041
  8. [8] F. De Terán, F. Dopico, and D.S. Mackey, Fiedler companion linearizations and the recovery of minimal indices, SIAM J. Matrix Anal. Appl., 31:4 (2010) 2181–2204.[WoS][Crossref] Zbl1205.15024
  9. [9] F. De Terán, F. Dopico, and J. Pérez, Condition numbers for inversion of Fiedler companion matrices, Linear Algebra Appl.439 (2013) 944–981.[WoS] Zbl1281.15004
  10. [10] B. Eastman, I.-J. Kim, B. Shader, and K.N. Vander Meulen, Companion matrix patterns, Linear Algebra Appl.463 (2014) 255–272.[WoS] Zbl1310.15015
  11. [11] M. Fiedler, A note on companion matrices, Linear Algebra Appl.372 (2003) 325–331. Zbl1031.15014
  12. [12] C. Garnett, B. Shader, C. Shader, and P. van den Driessche, Characterization of a family of generalized companion matrices Linear Algebra Appl. (2015), in press, .[Crossref] Zbl06570135
  13. [13] N.J. Higham, D.S. Mackey, N. Mackey, and F. Tisseur, Symmetric linearizations for matrix polynomials, SIAM J. Matrix Anal. Appl.29 (2006) 143–159.[WoS] Zbl1137.15006
  14. [14] C. Ma and X. Zhan, Extremal sparsity of the companion matrix of a polynomial, Linear Algebra Appl.438 (2013) 621–625.[WoS] Zbl1269.15007
  15. [15] S. Vologiannidis and E.N. Antoniou, A permuted factors approach for the linearization of polynomial matrices, Math. Control Signals Systems22 (2011) 317–342.[WoS] Zbl1248.93045

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.