Since its appearance, the D-stability characterization problem was claimed to be NP-hard and actually it was solved efficiently for matrices of very low orders only. Recently, we introduced a new approach which makes this problem numerically feasible, since the related algorithm shows a practical computational complexity which reveals polynomial. After some remarks on computational complexity theory, here we provide details about the computational complexity of D-stability characterization problem and its historical improvement.

D -stability characterization problem can exhibit a polynomial computational complexity

Raffaella Pavani
2019

Abstract

Since its appearance, the D-stability characterization problem was claimed to be NP-hard and actually it was solved efficiently for matrices of very low orders only. Recently, we introduced a new approach which makes this problem numerically feasible, since the related algorithm shows a practical computational complexity which reveals polynomial. After some remarks on computational complexity theory, here we provide details about the computational complexity of D-stability characterization problem and its historical improvement.
International Conference on Numerical Analysis and Applied Mathematics 2018, ICNAAM 2018
Computational complexity; polynomial complexity; D-stable matrix chracterization.
File in questo prodotto:
File Dimensione Formato  
PavaniAIPProcIcnaam2018.pdf

Accesso riservato

Descrizione: Articolo principale
: Publisher’s version
Dimensione 597.57 kB
Formato Adobe PDF
597.57 kB Adobe PDF   Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11311/1127587
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 1
social impact