Algebraic Geometric Methods For Solving Sparse Interpolation Problems

Interpolation is not only an essential research subject in computational mathematics but also widespread in engineering calculation. The sparse interpolation problem is interesting and has many important applications but not been extensively studied, and has received increasing attention to more and more foreign and domestic scholars.Finding solutions of a polynomial system is constantly an important and difficult problem, and it also is an essential research subject in algebra, algebraic geometry, computational mathematics and computer mathematics. In this dissertation, we give some properties of solutions of the polynomial system arising from sparse interpolation problems and finding a sparse solution of a class of differential equations with highly oscillatory coefficients which is closely related to the sparse interpolation problem, and propose efficient algorithms for solving them.In Chapter 1, we give a brief introduction of the development and application of the sparse interpolation problem, and the development of the homotopy method for finding all solutions of polynomial systems.In Chapter 2, we consider the equally spaced sparse interpolation problem. For the generic sampling, we have proved that the polynomial system arising from the sparse interpolation prob-lem with 2n equally spaced sampling points has just n! nonsingular and isolated solutions, and they belong to only one equivalence class in the sense of permutation. Utilizing these properties, we propose an efficient 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 for finding all isolated solutions of the polynomial system.In Chapter 3, for a general polynomial system with given group of variables, it is proved that if the highest ordered homogeneous part of it has only trivial solutions, then the number of isolated solutions of it is equal to the multi-homogeneous Bezout number. It is the theoretical basis of properties of the polynomial system arising from the equally spaced sparse interpolation problem with jump.In Chapter 4, we consider the equally spaced sparse interpolation problem with jump. For the polynomial system arising from this problem, we proposed a conjecture on the numbers of isolated solutions and equivalence classes, and we reduce the polynomial system by polynomial elimination and utilize homotopy method to prove the conjecture for some interesting cases. Then, we propose an efficient coefficient parameter homotopy method for finding all solutions of the polynomial system. It only needs a little computational cost in the first phase and the number of paths to be traced in the second phase is equal to that of equivalence classes of solutions, which is significantly fewer than that of isolated solutions.In Chapter 5, we consider the problem of finding a sparse solution of a class of linear elliptic differential equations with highly oscillatory coefficients. In contrast to traditional numerical methods (e.g. spectral methods, finite element methods), based on the observation that the exact solution can be well approximated by a linear combination of basis functions with relatively large coefficients, we utilize the discretization of using undetermined basis functions. So, similar to the sparse interpolation problem, it can be reduced to finding solutions of a class of small polynomial systems with particular structure instead of large liner problems. Based on it, we propose an efficient algorithm for the problem. Furthermore, the amount of computational work of our new method is independent of the parameter in the oscillatory coefficient.