Hits:

Indexed by:Journal Papers

Date of Publication:2016-01-01

Journal:SIAM JOURNAL ON NUMERICAL ANALYSIS

Included Journals:SCIE、EI

Volume:54

Issue:1

Page Number:462-480

ISSN No.:0036-1429

Key Words:sparse interpolation; polynomial system; homotopy method; global convergence

Abstract:In this paper, the solution of the polynomial system arising from sparse interpolation problems with equally spaced sampling is studied. Exploiting the special structure of the polynomial system, it is proved that all its solutions lie in one orbit for generic data. Then, based on the coefficient parameter homotopy method, an efficient algorithm for solving the system is proposed. Smoothness and accessibility of the coefficient parameter homotopy hold for the constant terms of the start system generated by a randomly chosen starting point. So, in the coefficient parameter homotopy method, it needs no computational cost in the first phase and only one path needs to be traced in the second phase. Preliminary numerical tests show that the proposed algorithm is promising.