×
Fukasaku, Ryoya; Iwane, Hidenao; Sato, Yosuke

On multivariate Hermitian quadratic forms. (English) Zbl 07095829

Math. Comput. Sci. 13, No. 1-2, 79-93 (2019).
Summary: Multivariate Hermitian quadratic forms play an important role in the real quantifier elimination algorithm based on the computation of comprehensive Gröbner systems introduced by V. Weispfenning and further improved by us. Our algorithm needs the computation of a certain type of saturation ideal in a parametric polynomial ring. In this paper, we study multivariate Hermitian quadratic forms in more detail and show several facts which have special importance in a parametric polynomial ring. Our results enable us to have an efficient method to compute the saturation ideal, which brings us a drastic improvement of our real quantifier elimination software.

Cited in 1 Document

MSC:

12D99 Real and complex fields

Keywords:

quantifier elimination; real closed field; comprehensive Gröbner system

Software:

QEPCAD; PGB; REDLOG; CGSQE
PDF BibTeX XML Cite
\textit{R. Fukasaku} et al., Math. Comput. Sci. 13, No. 1--2, 79--93 (2019; Zbl 07095829)
Full Text: DOI
  • logo of hbz
  • logo of WorldCat

References:

[1] Arai, N.H., Matsuzaki, T., Iwane, H., Anai, H.: Mathematics by machine. In: Proceedings of International Symposium on Symbolic and Algebraic Computation, pp. 1-8, ACM-Press (2014) · Zbl 1325.68212
[2] Becker, E., Wörmann, T.: On the trace formula for quadratic forms. In: Proceedings of Recent Advances in Real Algebraic Geometry and Quadratic Forms, Contemporary Mathematics, vol. 155, pp. 271-291. American Mathematical Society (1994)
[3] Brown, C., et al.: QEPCAD. https://urldefense.proofpoint.com/v2/url?u=https-3A__www.usna.edu_CS_qepcadweb_B_QEPCAD.html&d=DwICAg&c=vh6FgFnduejNhPPD0fl_yRaSfZy8CWbWnIf4XJhSqx8&r=UpNksRRkQEKvUbblp9QRYTuemGLwQgpW1U7iMCFPZ8k&m=mWR4kwzCQJx99sfByc_Wd_NtOKrvA94px0mf4a_qj_8&s=fs72Aj2MHHkrUbt5MXeOF0B3iyfTQkLWYjPboUB-RSA&e=. Accessed 8 Oct 2017
[4] Fukasaku, R.: 2016 Version of CGSQE Package. https://urldefense.proofpoint.com/v2/url?u=http-3A__www.rs.tus.ac.jp_fukasaku_software_CGSQE-2D20160509_&d=DwICAg&c=vh6FgFnduejNhPPD0fl_yRaSfZy8CWbWnIf4XJhSqx8&r=UpNksRRkQEKvUbblp9QRYTuemGLwQgpW1U7iMCFPZ8k&m=mWR4kwzCQJx99sfByc_Wd_NtOKrvA94px0mf4a_qj_8&s=ExGbD7jMK0fzhZjaF_9DQ2vYfqv6alRkPjcYhRzkADk&e=. Accessed 8 Oct 2017
[5] Fukasaku, R.: 2017 Version of CGSQE Package. https://urldefense.proofpoint.com/v2/url?u=http-3A__www.rs.tus.ac.jp_fukasaku_software_CGSQE-2D2017_&d=DwICAg&c=vh6FgFnduejNhPPD0fl_yRaSfZy8CWbWnIf4XJhSqx8&r=UpNksRRkQEKvUbblp9QRYTuemGLwQgpW1U7iMCFPZ8k&m=mWR4kwzCQJx99sfByc_Wd_NtOKrvA94px0mf4a_qj_8&s=E-8Gmc7etlgpy1LN6yFA1qKUNLLB65V2URmVednn2Rg&e=. Accessed 8 Oct 2017
[6] Collins, G.E.: Quantifier elimination for real closed fields by cylindrical algebraic decomposition. In: Proceedings of Automata Theory and Formal Languages, LNCS vol. 33, pp. 134-183. Springer, Berlin (1975)
[7] Fukasaku, R.: QE software based on comprehensive Gröbner systems. In: Proceedings of Mathematical Software—ICMS 2014—4th International Congress, LNCS vol. 8592, pp. 512-517. Springer, Berlin (2014) · Zbl 1434.68704
[8] Fukasaku, R., Iwane, H., Sato, Y: Real quantifier elimination by computation of comprehensive Gröbner systems. In: Proceedings of International Symposium on Symbolic and Algebraic Computation, pp. 173-180. ACM-Press (2015) · Zbl 1345.68282
[9] Fukasaku, R., Iwane, H., Sato, Y: On the Implementation of CGS Real QE. In: Proceedings of Mathematical Software—ICMS 2016—5th International Conference, LNCS vol. 9725, pp. 165-172. Springer, Berlin (2016) · Zbl 1434.68705
[10] Iwane, H.: SyNRAC Package. https://urldefense.proofpoint.com/v2/url?u=http-3A__www.fujitsu.com_jp_group_labs_en_resources_tech_freeware_synrac_&d=DwICAg&c=vh6FgFnduejNhPPD0fl_yRaSfZy8CWbWnIf4XJhSqx8&r=UpNksRRkQEKvUbblp9QRYTuemGLwQgpW1U7iMCFPZ8k&m=mWR4kwzCQJx99sfByc_Wd_NtOKrvA94px0mf4a_qj_8&s=ohEYZdyMb9fiZ7ajsP8WnI6QvqhisstydbZQtD1hGkM&e=. Accessed 8 Oct 2017
[11] Kapur, D., Sun, Y., Wang, D.: A new algorithm for computing comprehensive Gröbner systems. In: Proceedings of International Symposium on Symbolic and Algebraic Computation, pp. 29-36. ACM-Press (2010)
[12] Kurata, Y., Improving Suzuki-Sato’s CGS algorithm by using stability of Gröbner bases and basic manipulations for efficient implementation, Commun. Jpn. Soc. Symb. Algebr. Comput., 1, 39-66, (2011)
[13] Maza, M.-M. et al.: RegularChains Package. https://urldefense.proofpoint.com/v2/url?u=http-3A__www.regularchains.org_&d=DwICAg&c=vh6FgFnduejNhPPD0fl_yRaSfZy8CWbWnIf4XJhSqx8&r=UpNksRRkQEKvUbblp9QRYTuemGLwQgpW1U7iMCFPZ8k&m=mWR4kwzCQJx99sfByc_Wd_NtOKrvA94px0mf4a_qj_8&s=NJ2uBtKt_hCxEF7lQWZjZVvTVQSMTWIHFjDD-FsbidA&e=. Accessed 8 Oct 2017
[14] Nabeshima, K.: A speed-up of the algorithm for computing comprehensive Gröbner systems. In: Proceedings of the International Symposium on Symbolic and Algebraic Computation, pp. 299-306. ACM-Press (2007) · Zbl 1190.13025
[15] Nabeshima, K.: Stability conditions of monomial bases and comprehensive Gröbner systems. In: Proceedings of Computer Algebra in Scientific Computing, LNCS vol. 7442, pp. 248-259. Springer, Berlin (2012) · Zbl 1373.13030
[16] Pedersen, P., Roy, M.-F., Szpirglas, A.: Counting real zeroes in the multivariate case. In: Proceedings of Effective Methods in Algebraic Geometry, Progress in Mathematics vol. 109, pp. 203-224. Springer, Berlin (1993) · Zbl 0806.14042
[17] Sato, S., Fukasaku, R., Sekigawa, H.: On continuity of the roots of a parametric zero dimensional multivariate polynomial ideal. In: Proceedings of the International Symposium on Symbolic and Algebraic Computation, pp. 359-365. ACM-Press (2018)
[18] Strzebonski, A.: Reduce of Mathematica. https://urldefense.proofpoint.com/v2/url?u=https-3A__reference.wolfram.com_language_ref_Reduce.html&d=DwICAg&c=vh6FgFnduejNhPPD0fl_yRaSfZy8CWbWnIf4XJhSqx8&r=UpNksRRkQEKvUbblp9QRYTuemGLwQgpW1U7iMCFPZ8k&m=mWR4kwzCQJx99sfByc_Wd_NtOKrvA94px0mf4a_qj_8&s=4EgFsOWDHosP2kivGNaEgtF21HCLwzXqfkkgmrzY7SI&e=. Accessed 8 Oct 2017
[19] Strzebonski, A.: Resolve of Mathematica. https://urldefense.proofpoint.com/v2/url?u=https-3A__reference.wolfram.com_language_ref_Resolve.html&d=DwICAg&c=vh6FgFnduejNhPPD0fl_yRaSfZy8CWbWnIf4XJhSqx8&r=UpNksRRkQEKvUbblp9QRYTuemGLwQgpW1U7iMCFPZ8k&m=mWR4kwzCQJx99sfByc_Wd_NtOKrvA94px0mf4a_qj_8&s=f-nt87scWnkm1Ct-Hg0T9_eYCwKRzyOsZBx-bnIlD10&e=. Accessed 8 Oct 2017
[20] Strzebonski, A., Solving systems of strict polynomial inequalities, J. Symb. Comput., 29, 471-480, (2000) · Zbl 0962.68183
[21] Sturm, T. et al.: Redlog package. https://urldefense.proofpoint.com/v2/url?u=http-3A__www.redlog.eu_&d=DwICAg&c=vh6FgFnduejNhPPD0fl_yRaSfZy8CWbWnIf4XJhSqx8&r=UpNksRRkQEKvUbblp9QRYTuemGLwQgpW1U7iMCFPZ8k&m=mWR4kwzCQJx99sfByc_Wd_NtOKrvA94px0mf4a_qj_8&s=IYEAxvdgb7Rlopn5s55MJGTASSLXMa0Tr395COkW5Ww&e=. Accessed 8 Oct 2017
[22] Suzuki, A., Sato, Y.: A simple algorithm to compute comprehensive Gröbner bases using Gröbner bases. In: Proceedings of International Symposium on Symbolic and Algebraic Computation, pp. 326-331. ACM-Press (2006)
[23] Weispfenning, V.: A new approach to quantifier elimination for real algebra. In: Quantifier Elimination and Cylindrical Algebraic Decomposition, pp. 376-392. Springer, Berlin (1998) · Zbl 0900.03046
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.