Construction of efficient algorithms for quantifier elimination and their application to solving industrial problems
| Reference No. | 2022a005 |
|---|---|
| Type/Category | Grant for Young Researchers and Students-Short-term Joint Research |
| Title of Research Project | Construction of efficient algorithms for quantifier elimination and their application to solving industrial problems |
| Principal Investigator | Yuki Ishihara（Tokyo University of Science, Faculty of Science Division I, Department of Applied Mathematics / Assistant Professor） |
| Research Period |
October 31, 2022. - November 04, 2022. |
| Keyword(s) of Research Fields | Quantifier Elimination, Gröbner Basis, Comprehensive Gröbner System, Cylindrical Algebraic Decomposition, Primary Decomposition, Computer Algebra, Real Algebraic Geometry |
| Abstract for Research Report | Quantifier Elimination (QE) is one of the powerful methods for solving problems defined by algebraic equations and inequalities. QE has been implemented on computer algebra systems such as Maple and Mathematica.This research focuses on building efficient algorithms for QE and applying them to various problems that appear in industry. QE is a highly versatile technology that has been applied in a wide range of fields, including mathematical optimization, control system design, and automatic mathematical solution systems. One of the characteristics of the method using QE is that it is easy to analyze the mathematical structure behind the problem through symbolic computations. For example, QE can be applied to nonlinear or non-convex optimization problems that are difficult to handle numerically. In fact, the CREST research project "Construction of a Robust Optimization Platform Based on Hybrid Numerical/Symbolic Computation (Principal Investigator: Hirokazu Anai)" from 2003 to 2009 has achieved multi-objective optimization and robust optimization for problems appearing in industry, such as HDD shape optimization and optimal SRAM design. Many various applications of QE are also described in the technical book "Algorithms of Quantifier Elimination and Their Applications - Optimization by Symbolic and Algebraic Methods" (written by Hirokazu Anai and Kazuhiro Yokoyama, University of Tokyo Press). Despite its versatility, QE has the disadvantage of being computationally expensive compared to numerical computations. The objective of this study is to devise efficient programs for QE to solve various problems that appear in industry. For example, the methods will utilize primary decomposition for the existing QE algorithms. The expected results of this research are mainly the following three. (1) Development of efficient algorithms for QE (2) Improvement of basic algorithms used in Computer Algebra (3) Solving problems needed in industry |
| Organizing Committee Members (Workshop) Participants (Short-term Joint Usage) |
Yuki Ishihara（Tokyo University of Science, Faculty of Science Division I, Department of Applied Mathematics / Assistant Professor） Ryoya Fukasaku（Kyushu University, Faculty of Mathematics / Assistant Professor） Yasuhiko Ikematsu（Kyushu University, Institute of Mathematics for Industry / Assistant Professor） Yuta Kambe（Rikkyo University, Faculty of Science, Department of Mathematics / Research Assistant） Hidenao Iwane（Reading Skill Test, Inc. / Employee） |
| Adviser | Kazuhiro Yokoyama(College of Science, Rikkyo University / Professor) |