Minimal condition number for positive definite Hankel matrices using semidefinite programming

Suliman Al-Homidan; Mohammad M. Alshahrani; Cosmin G. Petra; Florian A. Potra

doi:10.1016/j.laa.2010.04.052

Minimal condition number for positive definite Hankel matrices using semidefinite programming

Suliman Al-Homidan
, Mohammad M. Alshahrani
, Cosmin G. Petra
, Florian A. Potra

Research output: Contribution to journal › Article › peer-review

2 Scopus citations

Abstract

We present a semidefinite programming approach for computing optimally conditioned positive definite Hankel matrices of order n. Unlike previous approaches, our method is guaranteed to find an optimally conditioned positive definite Hankel matrix within any desired tolerance. Since the condition number of such matrices grows exponentially with n, this is a very good test problem for checking the numerical accuracy of semidefinite programming solvers. Our tests show that semidefinite programming solvers using fixed double precision arithmetic are not able to solve problems with n>30. Moreover, the accuracy of the results for 24≤n≤30 is questionable. In order to accurately compute minimal condition number positive definite Hankel matrices of higher order, we use a Mathematica 6.0 implementation of the SDPHA solver that performs the numerical calculations in arbitrary precision arithmetic. By using this code, we have validated the results obtained by standard codes for n≤24, and we have found optimally conditioned positive definite Hankel matrices up to n=100.

Original language	English
Pages (from-to)	1101-1109
Number of pages	9
Journal	Linear Algebra and Its Applications
Volume	433
Issue number	6
DOIs	https://doi.org/10.1016/j.laa.2010.04.052
State	Published - 1 Nov 2010

Bibliographical note

Funding Information:
E-mail addresses: [email protected] (S. Al-Homidan), [email protected] (M.M. Alshahrani), cpetra1@math. umbc.edu (C.G. Petra), [email protected] (F.A. Potra). 1 Research supported by King Fahd University of Petroleum and Minerals (KFUPM). 2 Research supported in part by the National Science Foundation under Grant 0728878.

Keywords

Hankel matrix
Minimum condition number
Semi-definite programming

ASJC Scopus subject areas

Algebra and Number Theory
Numerical Analysis
Geometry and Topology
Discrete Mathematics and Combinatorics

Access to Document

10.1016/j.laa.2010.04.052

Cite this

@article{d9b77079c73b4c18a1c5d25063473981,

title = "Minimal condition number for positive definite Hankel matrices using semidefinite programming",

abstract = "We present a semidefinite programming approach for computing optimally conditioned positive definite Hankel matrices of order n. Unlike previous approaches, our method is guaranteed to find an optimally conditioned positive definite Hankel matrix within any desired tolerance. Since the condition number of such matrices grows exponentially with n, this is a very good test problem for checking the numerical accuracy of semidefinite programming solvers. Our tests show that semidefinite programming solvers using fixed double precision arithmetic are not able to solve problems with n>30. Moreover, the accuracy of the results for 24≤n≤30 is questionable. In order to accurately compute minimal condition number positive definite Hankel matrices of higher order, we use a Mathematica 6.0 implementation of the SDPHA solver that performs the numerical calculations in arbitrary precision arithmetic. By using this code, we have validated the results obtained by standard codes for n≤24, and we have found optimally conditioned positive definite Hankel matrices up to n=100.",

keywords = "Hankel matrix, Minimum condition number, Semi-definite programming",

author = "Suliman Al-Homidan and Alshahrani, \{Mohammad M.\} and Petra, \{Cosmin G.\} and Potra, \{Florian A.\}",

note = "Funding Information: E-mail addresses: [email protected] (S. Al-Homidan), [email protected] (M.M. Alshahrani), cpetra1@math. umbc.edu (C.G. Petra), [email protected] (F.A. Potra). 1 Research supported by King Fahd University of Petroleum and Minerals (KFUPM). 2 Research supported in part by the National Science Foundation under Grant 0728878.",

year = "2010",

month = nov,

day = "1",

doi = "10.1016/j.laa.2010.04.052",

language = "English",

volume = "433",

pages = "1101--1109",

journal = "Linear Algebra and Its Applications",

issn = "0024-3795",

publisher = "Elsevier Inc.",

number = "6",

}

TY - JOUR

T1 - Minimal condition number for positive definite Hankel matrices using semidefinite programming

AU - Al-Homidan, Suliman

AU - Alshahrani, Mohammad M.

AU - Petra, Cosmin G.

AU - Potra, Florian A.

N1 - Funding Information: E-mail addresses: [email protected] (S. Al-Homidan), [email protected] (M.M. Alshahrani), cpetra1@math. umbc.edu (C.G. Petra), [email protected] (F.A. Potra). 1 Research supported by King Fahd University of Petroleum and Minerals (KFUPM). 2 Research supported in part by the National Science Foundation under Grant 0728878.

PY - 2010/11/1

Y1 - 2010/11/1

N2 - We present a semidefinite programming approach for computing optimally conditioned positive definite Hankel matrices of order n. Unlike previous approaches, our method is guaranteed to find an optimally conditioned positive definite Hankel matrix within any desired tolerance. Since the condition number of such matrices grows exponentially with n, this is a very good test problem for checking the numerical accuracy of semidefinite programming solvers. Our tests show that semidefinite programming solvers using fixed double precision arithmetic are not able to solve problems with n>30. Moreover, the accuracy of the results for 24≤n≤30 is questionable. In order to accurately compute minimal condition number positive definite Hankel matrices of higher order, we use a Mathematica 6.0 implementation of the SDPHA solver that performs the numerical calculations in arbitrary precision arithmetic. By using this code, we have validated the results obtained by standard codes for n≤24, and we have found optimally conditioned positive definite Hankel matrices up to n=100.

AB - We present a semidefinite programming approach for computing optimally conditioned positive definite Hankel matrices of order n. Unlike previous approaches, our method is guaranteed to find an optimally conditioned positive definite Hankel matrix within any desired tolerance. Since the condition number of such matrices grows exponentially with n, this is a very good test problem for checking the numerical accuracy of semidefinite programming solvers. Our tests show that semidefinite programming solvers using fixed double precision arithmetic are not able to solve problems with n>30. Moreover, the accuracy of the results for 24≤n≤30 is questionable. In order to accurately compute minimal condition number positive definite Hankel matrices of higher order, we use a Mathematica 6.0 implementation of the SDPHA solver that performs the numerical calculations in arbitrary precision arithmetic. By using this code, we have validated the results obtained by standard codes for n≤24, and we have found optimally conditioned positive definite Hankel matrices up to n=100.

KW - Hankel matrix

KW - Minimum condition number

KW - Semi-definite programming

UR - https://www.scopus.com/pages/publications/77955423054

U2 - 10.1016/j.laa.2010.04.052

DO - 10.1016/j.laa.2010.04.052

M3 - Article

AN - SCOPUS:77955423054

SN - 0024-3795

VL - 433

SP - 1101

EP - 1109

JO - Linear Algebra and Its Applications

JF - Linear Algebra and Its Applications

IS - 6

ER -

Minimal condition number for positive definite Hankel matrices using semidefinite programming

Abstract

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Fingerprint

Cite this