Lower bounds for approximate factorizations via semidefinite programming (extended abstract)

Erich Kaltofen; Bin Li; Kartik Sivaramakrishnan; Zhengfeng Yang; Lihong Zhi

doi:10.1145/1277500.1277532

Lower bounds for approximate factorizations via semidefinite programming (extended abstract)

Erich Kaltofen^*
, Bin Li
, Kartik Sivaramakrishnan
, Zhengfeng Yang
, Lihong Zhi

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

1 Scopus citations

Abstract

The problem of approximately factoring a real or complex multivariate polynomial f seeks minimal perturbations Δf to the coefficients of the input polynomial f so that the deformed polynomial f + Δf has the desired factorization properties. Efficient algorithms exist that compute the nearest real or complex polynomial that has non-trivial factors (see [3, 6] and the literature cited there). Here we consider the solution of the arising optimization problems using polynomial optimization (POP) via semidefinite programming (SDP).We restrict to real coefficients in the input and output polynomials.

Original language	English
Title of host publication	SNC'07 - Proceedings of the 2007 International Workshop on Symbolic-Numeric Computation
Pages	203-204
Number of pages	2
DOIs	https://doi.org/10.1145/1277500.1277532
State	Published - 2007
Externally published	Yes
Event	SNC'07 - 2007 International Workshop on Symbolic-Numeric Computation - London, ON, Canada Duration: 25 Jul 2007 → 27 Jul 2007

Publication series

Name	SNC'07 - Proceedings of the 2007 International Workshop on Symbolic-Numeric Computation

Conference

Conference	SNC'07 - 2007 International Workshop on Symbolic-Numeric Computation
Country/Territory	Canada
City	London, ON
Period	25/07/07 → 27/07/07

Keywords

Approximate factorization
Hybrid method
SDP

Access to Document

10.1145/1277500.1277532

Cite this

Kaltofen, E., Li, B., Sivaramakrishnan, K., Yang, Z., & Zhi, L. (2007). Lower bounds for approximate factorizations via semidefinite programming (extended abstract). In SNC'07 - Proceedings of the 2007 International Workshop on Symbolic-Numeric Computation (pp. 203-204). (SNC'07 - Proceedings of the 2007 International Workshop on Symbolic-Numeric Computation). https://doi.org/10.1145/1277500.1277532

@inproceedings{3095bacb729b43e3ad54dfc4e7423639,

title = "Lower bounds for approximate factorizations via semidefinite programming (extended abstract)",

abstract = "The problem of approximately factoring a real or complex multivariate polynomial f seeks minimal perturbations Δf to the coefficients of the input polynomial f so that the deformed polynomial f + Δf has the desired factorization properties. Efficient algorithms exist that compute the nearest real or complex polynomial that has non-trivial factors (see [3, 6] and the literature cited there). Here we consider the solution of the arising optimization problems using polynomial optimization (POP) via semidefinite programming (SDP).We restrict to real coefficients in the input and output polynomials.",

keywords = "Approximate factorization, Hybrid method, SDP",

author = "Erich Kaltofen and Bin Li and Kartik Sivaramakrishnan and Zhengfeng Yang and Lihong Zhi",

year = "2007",

doi = "10.1145/1277500.1277532",

language = "英语",

isbn = "1595937447",

series = "SNC'07 - Proceedings of the 2007 International Workshop on Symbolic-Numeric Computation",

pages = "203--204",

booktitle = "SNC'07 - Proceedings of the 2007 International Workshop on Symbolic-Numeric Computation",

note = "SNC'07 - 2007 International Workshop on Symbolic-Numeric Computation ; Conference date: 25-07-2007 Through 27-07-2007",

}

Kaltofen, E, Li, B, Sivaramakrishnan, K, Yang, Z & Zhi, L 2007, Lower bounds for approximate factorizations via semidefinite programming (extended abstract). in SNC'07 - Proceedings of the 2007 International Workshop on Symbolic-Numeric Computation. SNC'07 - Proceedings of the 2007 International Workshop on Symbolic-Numeric Computation, pp. 203-204, SNC'07 - 2007 International Workshop on Symbolic-Numeric Computation, London, ON, Canada, 25/07/07. https://doi.org/10.1145/1277500.1277532

Lower bounds for approximate factorizations via semidefinite programming (extended abstract). / Kaltofen, Erich; Li, Bin; Sivaramakrishnan, Kartik et al.
SNC'07 - Proceedings of the 2007 International Workshop on Symbolic-Numeric Computation. 2007. p. 203-204 (SNC'07 - Proceedings of the 2007 International Workshop on Symbolic-Numeric Computation).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Lower bounds for approximate factorizations via semidefinite programming (extended abstract)

AU - Kaltofen, Erich

AU - Li, Bin

AU - Sivaramakrishnan, Kartik

AU - Yang, Zhengfeng

AU - Zhi, Lihong

PY - 2007

Y1 - 2007

N2 - The problem of approximately factoring a real or complex multivariate polynomial f seeks minimal perturbations Δf to the coefficients of the input polynomial f so that the deformed polynomial f + Δf has the desired factorization properties. Efficient algorithms exist that compute the nearest real or complex polynomial that has non-trivial factors (see [3, 6] and the literature cited there). Here we consider the solution of the arising optimization problems using polynomial optimization (POP) via semidefinite programming (SDP).We restrict to real coefficients in the input and output polynomials.

AB - The problem of approximately factoring a real or complex multivariate polynomial f seeks minimal perturbations Δf to the coefficients of the input polynomial f so that the deformed polynomial f + Δf has the desired factorization properties. Efficient algorithms exist that compute the nearest real or complex polynomial that has non-trivial factors (see [3, 6] and the literature cited there). Here we consider the solution of the arising optimization problems using polynomial optimization (POP) via semidefinite programming (SDP).We restrict to real coefficients in the input and output polynomials.

KW - Approximate factorization

KW - Hybrid method

KW - SDP

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

U2 - 10.1145/1277500.1277532

DO - 10.1145/1277500.1277532

M3 - 会议稿件

AN - SCOPUS:36448971198

SN - 1595937447

SN - 9781595937445

T3 - SNC'07 - Proceedings of the 2007 International Workshop on Symbolic-Numeric Computation

SP - 203

EP - 204

BT - SNC'07 - Proceedings of the 2007 International Workshop on Symbolic-Numeric Computation

T2 - SNC'07 - 2007 International Workshop on Symbolic-Numeric Computation

Y2 - 25 July 2007 through 27 July 2007

ER -

Kaltofen E, Li B, Sivaramakrishnan K, Yang Z, Zhi L. Lower bounds for approximate factorizations via semidefinite programming (extended abstract). In SNC'07 - Proceedings of the 2007 International Workshop on Symbolic-Numeric Computation. 2007. p. 203-204. (SNC'07 - Proceedings of the 2007 International Workshop on Symbolic-Numeric Computation). doi: 10.1145/1277500.1277532

Lower bounds for approximate factorizations via semidefinite programming (extended abstract)

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this