@article{hong_yang_2024, title={Parametric "non-nested" discriminants for multiplicities of univariate polynomials}, volume={3}, ISSN={["1869-1862"]}, DOI={10.1007/s11425-023-2143-3}, journal={SCIENCE CHINA-MATHEMATICS}, author={Hong, Hoon and Yang, Jing}, year={2024}, month={Mar} } @article{hong_ovchinnikov_pogudin_yap_2023, title={Global Identifiability of Differential Models (vol 73, pg 1831, 2020)}, volume={9}, ISSN={["1097-0312"]}, DOI={10.1002/cpa.22163}, abstractNote={We are grateful to Peter Thompson for pointing out an error in [1, Lemma 3.5, p. 1848]. The original proof worked only under the assumption that θ ̂ $\hat{\theta }$ is a vector of constants. However, some of the components of θ ̂ $\hat{\bm{\theta }}$ could be the states of the dynamic under consideration, and the lemma was used in such a setup (i.e., with θ ̂ $\hat{\bm{\theta }}$ involving states) later in [1, Proposition 3.4]. We give a more explicit version of the statement and provide a correct proof. The desired statement will be deduced from the following: Lemma 1.Consider a system of differential equations Proof.Consider the following differential ideal Now we will prove the claim. Consider the ring R : = C [ x , μ ] { u } [ 1 / Q ] $R := \mathbb {C}[\bm{x}, \bm{\mu }]\lbrace \bm{u}\rbrace [1/Q]$ . Let J be the ideal generated by I ∩ C [ x , μ ] { u } $I \cap \mathbb {C}[\bm{x}, \bm{\mu }]\lbrace \bm{u}\rbrace$ in R. The definition of I via the saturation at Q implies that Let R ∼ $\widetilde{R}$ be the localization of R with respect to C { u } $\mathbb {C}\lbrace \bm{u}\rbrace$ and J ∼ $\widetilde{J}$ be the ideal generated by J in this localization. The derivation L $\mathcal {L}$ can be naturally extended to R ∼ $\widetilde{R}$ , and J ∼ $\widetilde{J}$ is also L $\mathcal {L}$ -invariant. It is sufficient to prove that J ∼ ∩ C [ x , μ ] ≠ { 0 } $\widetilde{J}\cap \mathbb {C}[\bm{x}, \bm{\mu }] \ne \lbrace 0\rbrace$ . Consider a nonzero element of J ∼ ∩ C [ x , μ ] { u } $\widetilde{J} \cap \mathbb {C}[\bm{x}, \bm{\mu }]\lbrace \bm{u}\rbrace$ with the smallest number of monomials and, among such elements, an element of the smallest total degree. We will call it S. If S ∈ C [ x , μ ] $S\in \mathbb {C}[\bm{x}, \bm{\mu }]$ , we are done. Otherwise, one of u appears in S, say u1. Let h = ord u 1 S $h = \operatorname{ord}_{u_1}S$ . Since R ∼ $\widetilde{R}$ is a Noetherian ring, there exists N > 0 $N > 0$ such that The following corollary is equivalent to [1, Lemma 3.5, p. 1848] but explicitly highlights that some of the entries of θ ̂ $\hat{\bm{\theta }}$ may be initial conditions, not only system parameters. Corollary 1. (Clarified version of [[1], Lemma 3.5, p. 1848])In the notation of [1, Section 2.2], let P ( μ , x , u , … , u ( N ) ) ∈ C [ μ , x ] { u } $P(\bm{\mu }, \bm{x}, u, \ldots , u^{(N)})\in \mathbb {C}[\bm{\mu }, \bm{x}] \lbrace u \rbrace$ be nonzero. Then there exist nonempty Zariski open subsets Θ ⊂ C s $\Theta {\subset }\mathbb {C}^{s}$ and U ⊂ C ∞ ( 0 ) $U\subset \mathbb {C}^{\infty }(0)$ such that, for every θ ̂ = ( μ ̂ , x ̂ * ) ∈ Θ $\hat{\bm{\theta }} = (\hat{\bm{\mu }}, \hat{\bm{x}}^\ast )\in \Theta$ , u ̂ ∈ U $\hat{u}\in U$ , and the corresponding x ̂ = X ( θ ̂ , u ̂ ) $\hat{\bm{x}} = X(\hat{\bm{\theta }}, \hat{u})$ , the function P ( μ ̂ , x ̂ , u ̂ , … , ( u ̂ ) ( N ) ) $P(\hat{\bm{\mu }}, \hat{\bm{x}}, \hat{u},\ldots ,(\hat{u})^{(N)})$ is a nonzero element of C ∞ ( 0 ) $\mathbb {C}^{\infty }(0)$ . Proof.We apply Lemma 1 to the model Σ and the polynomial P as in the statement, and obtain polynomials P 1 ( x , μ ) $P_1(\bm{x}, \bm{\mu })$ and P2(u). We define Zariski open sets Θ and U by P 1 ≠ 0 $P_1 \ne 0$ and P 2 ( u ) | t = 0 ≠ 0 $P_2(\bm{u})|_{t = 0} \ne 0$ , respectively. Then the lemma implies that, for ( μ ̂ , x ̂ ∗ ) ∈ Θ $(\hat{\bm{\mu }}, \hat{\bm{x}}^*) \in \Theta$ and u ̂ ∈ U $\hat{u} \in U$ , P ( μ ̂ , x ̂ , u ̂ , … , ( u ̂ ) ( N ) ) $P(\hat{\bm{\mu }}, \hat{\bm{x}}, \hat{u},\ldots ,(\hat{u})^{(N)})$ will be a nonzero function. □ $\Box$}, journal={COMMUNICATIONS ON PURE AND APPLIED MATHEMATICS}, author={Hong, Hoon and Ovchinnikov, Alexey and Pogudin, Gleb and Yap, Chee}, year={2023}, month={Sep} } @article{hong_wang_yang_2023, title={Improving Angular Speed Uniformity by Piecewise Radical Reparameterization}, volume={398}, ISSN={["2075-2180"]}, DOI={10.4204/EPTCS.398.19}, abstractNote={For a rational parameterization of a curve, it is desirable that its angular speed is as uniform as possible. Hence, given a rational parameterization, one wants to find re-parameterization with better uniformity. One natural way is to use piecewise rational reparameterization. However, it turns out that the piecewise rational reparameterization does not help when the angular speed of the given rational parameterization is zero at some points on the curve. In this paper, we show how to overcome the challenge by using piecewise radical reparameterization.}, journal={ELECTRONIC PROCEEDINGS IN THEORETICAL COMPUTER SCIENCE}, author={Hong, Hoon and Wang, Dongming and Yang, Jing}, year={2023}, pages={165–178} } @article{hong_yang_2021, title={A condition for multiplicity structure of univariate polynomials}, volume={5}, DOI={10.1016/j.jsc.2020.08.007}, abstractNote={We consider the problem of finding a condition for a univariate polynomial having a given multiplicity structure when the number of distinct roots is given. It is well known that such conditions can be written as conjunctions of several polynomial equations and one inequation in the coefficients, by using repeated parametric gcd's. In this paper, we give a novel condition which is not based on repeated gcd's. Furthermore, it is shown that the number of polynomials in the condition is optimal and the degree of polynomials is smaller than that in the previous condition based on repeated gcd's.}, journal={Journal of Symbolic Computation}, author={Hong, Hoon and Yang, Jing}, year={2021}, month={May}, pages={15} } @article{hong_yang_2021, title={A condition for multiplicity structure of univariate polynomials}, volume={104}, url={https://www.sciencedirect.com/science/article/pii/S0747717120300882}, DOI={https://doi.org/10.1016/j.jsc.2020.08.007}, abstractNote={We consider the problem of finding a condition for a univariate polynomial having a given multiplicity structure when the number of distinct roots is given. It is well known that such conditions can be written as conjunctions of several polynomial equations and one inequation in the coefficients, by using repeated parametric gcd's. In this paper, we give a novel condition which is not based on repeated gcd's. Furthermore, it is shown that the number of polynomials in the condition is optimal and the degree of polynomials is smaller than that in the previous condition based on repeated gcd's.}, journal={Journal of Symbolic Computation}, author={Hong, Hoon and Yang, Jing}, year={2021}, pages={523–538} } @article{al-kateeb_ambrosino_hong_lee_2021, title={Maximum gap in cyclotomic polynomials}, volume={229}, ISSN={["1096-1658"]}, DOI={10.1016/j.jnt.2021.04.013}, abstractNote={We study the maximum gap g (maximum of the differences between any two consecutive exponents) of cyclotomic polynomials. In 2012, Hong, Lee, Lee and Park showed that g(Φp1p2)=p1−1 for primes p2>p1. In 2017, based on numerous calculations, the following generalization was conjectured: g(Φmp)=φ(m) for square free odd m and prime p>m. The main contribution of this paper is a proof of this conjecture. The proof is based on the discovery of an elegant structure among certain sub-polynomials of Φmp, which are divisible by the m-th inverse cyclotomic polynomial Ψm=xm−1Φm.}, journal={JOURNAL OF NUMBER THEORY}, author={Al-Kateeb, Ala'a and Ambrosino, Mary and Hong, Hoon and Lee, Eunjeong}, year={2021}, month={Dec}, pages={1–15} } @article{hong_ovchinnikov_pogudin_yap_2020, title={Global Identifiability of Differential Models}, volume={73}, ISSN={["1097-0312"]}, url={http://dx.doi.org/10.1002/cpa.21921}, DOI={10.1002/cpa.21921}, abstractNote={Many real‐world processes and phenomena are modeled using systems of ordinary differential equations with parameters. Given such a system, we say that a parameter is globally identifiable if it can be uniquely recovered from input and output data. The main contribution of this paper is to provide theory, an algorithm, and software for deciding global identifiability. First, we rigorously derive an algebraic criterion for global identifiability (this is an analytic property), which yields a deterministic algorithm. Second, we improve the efficiency by randomizing the algorithm while guaranteeing the probability of correctness. With our new algorithm, we can tackle problems that could not be tackled before. A software based on the algorithm (called SIAN) is available at https://github.com/pogudingleb/SIAN. © 2020 Wiley Periodicals LLC}, number={9}, journal={COMMUNICATIONS ON PURE AND APPLIED MATHEMATICS}, publisher={Wiley}, author={Hong, Hoon and Ovchinnikov, Alexey and Pogudin, Gleb and Yap, Chee}, year={2020}, month={Sep}, pages={1831–1879} } @article{hong_ovchinnikov_pogudin_yap_2019, title={SIAN: a tool for assessing structural identifiability of parametric ODEs}, volume={53}, ISSN={["1932-2240"]}, url={https://doi.org/10.1145/3371991.3371993}, DOI={10.1145/3371991.3371993}, abstractNote={Many important real-world processes are modeled using systems of ordinary differential equations (ODEs) involving unknown parameters. The values of these parameters are usually inferred from experimental data. However, due to the structure of the model, there might be multiple parameter values that yield the same observed behavior even in the case of continuous noise-free data. It is important to detect such situations a priori, before collecting actual data. In this case, the only input is the model itself, so it is natural to tackle this question by methods of symbolic computation.}, number={2}, journal={ACM COMMUNICATIONS IN COMPUTER ALGEBRA}, author={Hong, Hoon and Ovchinnikov, Alexey and Pogudin, Gleb and Yap, Chee}, year={2019}, month={Jun}, pages={37–40} } @article{hong_ovchinnikov_pogudin_yap_2019, title={SIAN: software for structural identifiability analysis of ODE models}, volume={35}, ISSN={["1460-2059"]}, url={http://dx.doi.org/10.1093/bioinformatics/bty1069}, DOI={10.1093/bioinformatics/bty1069}, abstractNote={Abstract}, number={16}, journal={BIOINFORMATICS}, publisher={Oxford University Press (OUP)}, author={Hong, Hoon and Ovchinnikov, Alexey and Pogudin, Gleb and Yap, Chee}, editor={Wren, JonathanEditor}, year={2019}, month={Aug}, pages={2873–2874} } @article{herman_hong_tsigaridas_2018, title={Improving root separation bounds}, volume={84}, ISSN={["0747-7171"]}, url={http://dx.doi.org/10.1016/j.jsc.2017.03.001}, DOI={10.1016/j.jsc.2017.03.001}, abstractNote={Let f be a polynomial (or polynomial system) with all simple roots. The root separation of f is the minimum of the pair-wise distances between the complex roots. A root separation bound is a lower bound on the root separation. Finding a root separation bound is a fundamental problem, arising in numerous disciplines. We present two new root separation bounds: one univariate bound, and one multivariate bound. The new bounds improve on the old bounds in two ways: The new bounds are usually significantly bigger (hence better) than the previous bounds. The new bounds scale correctly, unlike the previous bounds.}, journal={JOURNAL OF SYMBOLIC COMPUTATION}, publisher={Elsevier BV}, author={Herman, Aaron and Hong, Hoon and Tsigaridas, Elias}, year={2018}, pages={25–56} } @article{coss_hauenstein_hong_molzahn_2018, title={Locating and Counting Equilibria of the Kuramoto Model with Rank-One Coupling}, volume={2}, ISSN={["2470-6566"]}, url={http://dx.doi.org/10.1137/17m1128198}, DOI={10.1137/17m1128198}, abstractNote={The Kuramoto model describes synchronization behavior among coupled oscillators and enjoys successful application in a wide variety of fields. Many of these applications seek phase-coherent solutions, i.e., equilibria of the model. Historically, research has focused on situations where the number of oscillators, $n$, is extremely large and can be treated as being infinite. More recently, however, applications have arisen in areas such as electrical engineering with more modest values of $n$. For these, the equilibria can be located by finding the real solutions of a system of polynomial equations utilizing techniques from algebraic geometry. However, typical methods for solving such systems locate all complex solutions even though only the real solutions give equilibria. In this paper, we present an algorithm to locate only the real solutions of the model, thereby shortening computation time by several orders of magnitude in certain situations. This is accomplished by choosing specific equilibria representatives and the consequent algebraic decoupling of the system. The correctness of the algorithm (that it finds only and all the equilibria) is proved rigorously. Additionally, the algorithm can be implemented using interval methods so that the equilibria can be approximated up to any given precision without significantly more computational effort. We also compare this solving approach to other computational algebraic geometric methods. Furthermore, analyzing this approach allows us to prove, asymptotically, that the maximum number of equilibria grows at the same rate as the number of complex solutions of a corresponding polynomial system. Finally, we conjecture an upper bound on the maximum number of equilibria for any number of oscillators which generalizes the known cases and is obtained on a range of explicitly provided natural frequencies.}, number={1}, journal={SIAM JOURNAL ON APPLIED ALGEBRA AND GEOMETRY}, publisher={Society for Industrial & Applied Mathematics (SIAM)}, author={Coss, Owen and Hauenstein, Jonathan D. and Hong, Hoon and Molzahn, Daniel K.}, year={2018}, pages={45–71} } @article{hong_rafael sendra_2018, title={Number of common roots and resultant of two tropical univariate polynomials}, volume={511}, ISSN={["1090-266X"]}, url={http://dx.doi.org/10.1016/j.jalgebra.2018.06.027}, DOI={10.1016/j.jalgebra.2018.06.027}, abstractNote={It is well known that for two univariate polynomials over the complex number field the number of their common roots is equal to the order of their resultant. In this paper, we show that this fundamental relationship still holds for the tropical polynomials under suitable adaptation of the notion of order, if the roots are simple and non-zero.}, journal={JOURNAL OF ALGEBRA}, publisher={Elsevier BV}, author={Hong, Hoon and Rafael Sendra, J.}, year={2018}, month={Oct}, pages={420–439} } @inproceedings{hong_sturm_2018, title={Positive Solutions of Systems of Signed Parametric Polynomial Inequalities}, volume={11077}, url={https://doi.org/10.1007/978-3-319-99639-4\_17}, DOI={10.1007/978-3-319-99639-4\_17}, booktitle={Computer Algebra in Scientific Computing - 20th International Workshop, CASC 2018, Lille, France, September 17-21, 2018, Proceedings}, publisher={Springer}, author={Hong, Hoon and Sturm, Thomas}, editor={Gerdt, Vladimir P. and Koepf, Wolfram and Seiler, Werner M. and Vorozhtsov, Evgenii V.Editors}, year={2018}, pages={238–253} } @article{hong_hough_kogan_2017, title={Algorithm for computing mu-bases of univariate polynomials}, volume={80}, ISSN={["0747-7171"]}, url={http://dx.doi.org/10.1016/j.jsc.2016.08.013}, DOI={10.1016/j.jsc.2016.08.013}, abstractNote={We present a new algorithm for computing a μ-basis of the syzygy module of n polynomials in one variable over an arbitrary field K. The algorithm is conceptually different from the previously-developed algorithms by Cox, Sederberg, Chen, Zheng, and Wang for n=3, and by Song and Goldman for an arbitrary n. The algorithm involves computing a "partial" reduced row-echelon form of a (2d+1)×n(d+1) matrix over K, where d is the maximum degree of the input polynomials. The proof of the algorithm is based on standard linear algebra and is completely self-contained. The proof includes a proof of the existence of the μ-basis and as a consequence provides an alternative proof of the freeness of the syzygy module. The theoretical (worst case asymptotic) computational complexity of the algorithm is O(d2n+d3+n2). We have implemented this algorithm (HHK) and the one developed by Song and Goldman (SG). Experiments on random inputs indicate that SG is faster than HHK when d is sufficiently large for a fixed n, and that HHK is faster than SG when n is sufficiently large for a fixed d.}, journal={JOURNAL OF SYMBOLIC COMPUTATION}, publisher={Elsevier BV}, author={Hong, Hoon and Hough, Zachary and Kogan, Irina A.}, year={2017}, pages={844–874} } @article{han_dai_hong_xia_2017, title={Open weak CAD and its applications}, volume={80}, ISSN={["0747-7171"]}, url={http://dx.doi.org/10.1016/j.jsc.2016.07.032}, DOI={10.1016/j.jsc.2016.07.032}, abstractNote={The concept of open weak CAD is introduced. Every open CAD is an open weak CAD. On the contrary, an open weak CAD is not necessarily an open CAD. An algorithm for computing projection polynomials of open weak CADs is proposed. The key idea is to compute the intersection of projection factor sets produced by different projection orders. The resulting open weak CAD often has smaller number of sample points than open CADs. The algorithm can be used for computing sample points for all open connected components of f≠0 for a given polynomial f. It can also be used for many other applications, such as testing semi-definiteness of polynomials and copositive problems. In fact, we solved several difficult semi-definiteness problems efficiently by using the algorithm. Furthermore, applying the algorithm to copositive problems, we find an explicit expression of the polynomials producing open weak CADs under some conditions, which significantly improves the efficiency of solving copositive problems.}, journal={JOURNAL OF SYMBOLIC COMPUTATION}, publisher={Elsevier BV}, author={Han, Jingjun and Dai, Liyun and Hong, Hoon and Xia, Bican}, year={2017}, pages={785–816} } @article{hong_kim_scholten_sendra_2017, title={Resultants over commutative idempotent semirings I: Algebraic aspect}, volume={79}, ISSN={["1095-855X"]}, url={http://dx.doi.org/10.1016/j.jsc.2016.02.009}, DOI={10.1016/j.jsc.2016.02.009}, abstractNote={The resultant theory plays a crucial role in computational algebra and algebraic geometry. The theory has two aspects: algebraic and geometric. In this paper, we focus on the algebraic aspect. One of the most important and well known algebraic properties of the resultant is that it is equal to the determinant of the Sylvester matrix. In 2008, Odagiri proved that a similar property holds over the tropical semiring if one replaces subtraction with addition. The tropical semiring belongs to a large family of algebraic structures called commutative idempotent semiring. In this paper, we prove that the same property (with subtraction replaced with addition) holds over an arbitrary commutative idempotent semiring.}, journal={JOURNAL OF SYMBOLIC COMPUTATION}, publisher={Elsevier BV}, author={Hong, Hoon and Kim, Yonggu and Scholten, Georgy and Sendra, J. Rafael}, year={2017}, pages={285–308} } @article{mccallum_hong_2016, title={On using Lazard's projection in CAD construction}, volume={72}, ISSN={["0747-7171"]}, url={http://dx.doi.org/10.1016/j.jsc.2015.02.001}, DOI={10.1016/j.jsc.2015.02.001}, abstractNote={In 1994 Lazard proposed an improved projection operation for cylindrical algebraic decomposition (CAD). For the proof he introduced a certain notion of valuation of a multivariate Puiseux series at a point. However a gap in one of the key supporting results for the improved projection was subsequently noticed. In this paper we show that Lazard's projection is valid for CAD construction for so-called well-oriented polynomial sets. Our proof does not make use of Lazard's notion of valuation, however.}, journal={JOURNAL OF SYMBOLIC COMPUTATION}, publisher={Elsevier BV}, author={McCallum, Scott and Hong, Hoon}, year={2016}, pages={65–81} } @article{herman_hong_2016, title={Quality of positive root bounds}, volume={74}, ISSN={["0747-7171"]}, url={http://dx.doi.org/10.1016/j.jsc.2015.09.006}, DOI={10.1016/j.jsc.2015.09.006}, abstractNote={In this paper, we study the quality of positive root bounds. A positive root bound of a polynomial is an upper bound on the largest positive root. Higher quality means that the relative over-estimation (the ratio of the bound and the largest positive root) is smaller. We report three findings. Most known positive root bounds can be arbitrarily bad; that is, the relative over-estimation can approach infinity, even when the degree and the coefficient size are fixed. When the number of sign variations is the same as the number of positive roots, the relative over-estimation of a positive root bound due to Hong (BH) is at most linear in the degree, no matter what the coefficient size is. When the number of sign variations is one, the relative over-estimation of BH is at most constant, in particular 4, no matter what the degree and the coefficient size are.}, journal={JOURNAL OF SYMBOLIC COMPUTATION}, publisher={Elsevier BV}, author={Herman, Aaron and Hong, Hoon}, year={2016}, pages={592–602} } @article{erascu_hong_2016, title={Real quantifier elimination for the synthesis of optimal numerical algorithms (Case study: Square root computation)}, volume={75}, ISSN={["0747-7171"]}, url={http://dx.doi.org/10.1016/j.jsc.2015.11.010}, DOI={10.1016/j.jsc.2015.11.010}, abstractNote={We report on our on-going efforts to apply real quantifier elimination to the synthesis of optimal numerical algorithms. In particular, we describe a case study on the square root problem: given a real number x and an error bound ε, find a real interval such that it contains x and its width is less than or equal to ε. A typical numerical algorithm starts with an initial interval and repeatedly updates it by applying a "refinement map" on it until it becomes narrow enough. Thus the synthesis amounts to finding a refinement map that ensures the correctness and optimality of the resulting algorithm. This problem can be formulated as a real quantifier elimination. Hence, in principle, the synthesis can be carried out automatically. However, the computational requirement is huge, making the automatic synthesis practically impossible with the current general real quantifier elimination software. We overcame the difficulty by (1) carefully reducing a complicated quantified formula into several simpler ones and (2) automatically eliminating the quantifiers from the resulting ones using the state-of-the-art quantifier elimination software. As the result, we were able to synthesize semi-automatically an optimal quadratically1 convergent map, which is better than the well known hand-crafted Secant-Newton map. Interestingly, the optimal synthesized map is not contracting as one would naturally expect.}, journal={JOURNAL OF SYMBOLIC COMPUTATION}, publisher={Elsevier BV}, author={Erascu, Madalina and Hong, Hoon}, year={2016}, pages={110–126} } @article{harlim_hong_robbins_2015, title={An algebraic method for constructing stable and consistent autoregressive filters}, volume={283}, ISSN={["1090-2716"]}, url={http://dx.doi.org/10.1016/j.jcp.2014.12.004}, DOI={10.1016/j.jcp.2014.12.004}, abstractNote={In this paper, we introduce an algebraic method to construct stable and consistent univariate autoregressive (AR) models of low order for filtering and predicting nonlinear turbulent signals with memory depth. By stable, we refer to the classical stability condition for the AR model. By consistent, we refer to the classical consistency constraints of Adams–Bashforth methods of order-two. One attractive feature of this algebraic method is that the model parameters can be obtained without directly knowing any training data set as opposed to many standard, regression-based parameterization methods. It takes only long-time average statistics as inputs. The proposed method provides a discretization time step interval which guarantees the existence of stable and consistent AR model and simultaneously produces the parameters for the AR models. In our numerical examples with two chaotic time series with different characteristics of decaying time scales, we find that the proposed AR models produce significantly more accurate short-term predictive skill and comparable filtering skill relative to the linear regression-based AR models. These encouraging results are robust across wide ranges of discretization times, observation times, and observation noise variances. Finally, we also find that the proposed model produces an improved short-time prediction relative to the linear regression-based AR-models in forecasting a data set that characterizes the variability of the Madden–Julian Oscillation, a dominant tropical atmospheric wave pattern.}, journal={JOURNAL OF COMPUTATIONAL PHYSICS}, publisher={Elsevier BV}, author={Harlim, John and Hong, Hoon and Robbins, Jacob L.}, year={2015}, month={Feb}, pages={241–257} } @article{hong_lee_lee_2015, title={Explicit formula for optimal ate pairing over cyclotomic family of elliptic curves}, volume={34}, ISSN={["1090-2465"]}, url={http://dx.doi.org/10.1016/j.ffa.2014.12.007}, DOI={10.1016/j.ffa.2014.12.007}, abstractNote={Pairings on elliptic curves play an important role in cryptography. We provide an explicit formula for vectors of polynomials describing optimal ate pairings over cyclotomic family of elliptic curves. The explicit formula is simple in that it only involves partitioning a certain cyclotomic polynomial. The simplicity of the formula allows us to analyze the sparsity of the vector.}, journal={FINITE FIELDS AND THEIR APPLICATIONS}, publisher={Elsevier BV}, author={Hong, Hoon and Lee, Eunjeong and Lee, Hyang-Sook}, year={2015}, month={Jul}, pages={45–74} } @article{hong_tang_xia_2015, title={Special algorithm for stability analysis of multistable biological regulatory systems}, volume={70}, ISSN={["0747-7171"]}, url={http://dx.doi.org/10.1016/j.jsc.2014.09.039}, DOI={10.1016/j.jsc.2014.09.039}, abstractNote={We consider the problem of counting (stable) equilibriums of an important family of algebraic differential equations modeling multistable biological regulatory systems. The problem can be solved, in principle, using real quantifier elimination algorithms, in particular real root classification algorithms. However, it is well known that they can handle only very small cases due to the enormous computing time requirements. In this paper, we present a special algorithm which is much more efficient than the general methods. Its efficiency comes from the exploitation of certain interesting structures of the family of differential equations.}, journal={JOURNAL OF SYMBOLIC COMPUTATION}, publisher={Elsevier BV}, author={Hong, Hoon and Tang, Xiaoxian and Xia, Bican}, year={2015}, pages={112–135} } @inbook{yang_wang_hong_2014, title={ImUp: A Maple Package for Uniformity-Improved Reparameterization of Plane Curves}, volume={10}, ISBN={9783662437988 9783662437995}, url={http://dx.doi.org/10.1007/978-3-662-43799-5_29}, DOI={10.1007/978-3-662-43799-5_29}, booktitle={Computer Mathematics}, publisher={Springer Berlin Heidelberg}, author={Yang, Jing and Wang, Dongming and Hong, Hoon}, year={2014}, pages={437–451} } @book{hong_yap_2014, title={Mathematical Software – ICMS 2014: 4th International Congress, Seoul, South Korea, August 5-9, 2014. Proceedings}, volume={8592}, url={https://doi.org/10.1007/978-3-662-44199-2}, DOI={10.1007/978-3-662-44199-2}, abstractNote={This book constitutes the proceedings of the 4th International Conference on Mathematical Software, ICMS 2014, held in Seoul, South Korea, in August 2014. The 108 papers included in this volume were c}, journal={Lecture Notes in Computer Science}, publisher={Springer}, author={Hong, Hoon and Yap, Chee}, editor={Hong, Hoon and Yap, CheeEditors}, year={2014}, month={Jan} } @book{hong_yap_2014, title={Mathematical software - ICMS 2014: 4th International Congress, Seoul, South Korea, August 5-9, 2014 : Proceedings}, publisher={Heidelberg: Springer}, year={2014} } @inbook{chang_hong_lee_lee_2014, title={Pairing Inversion via Non-degenerate Auxiliary Pairings}, ISBN={9783319048727 9783319048734}, ISSN={0302-9743 1611-3349}, url={http://dx.doi.org/10.1007/978-3-319-04873-4_5}, DOI={10.1007/978-3-319-04873-4_5}, abstractNote={The security of pairing-based cryptosystems is closely related to the difficulty of the pairing inversion problem(PI). In this paper, we discuss the difficulty of pairing inversion on the generalized ate pairings of Vercauteren. First, we provide a simpler approach for PI by generalizing and simplifying Kanayama-Okamoto’s approach; our approach involves modifications of exponentiation inversion(EI) and Miller inversion(MI), via an “auxiliary” pairing. Then we provide a complexity of the modified MI, showing that the complexity depends on the sum-norm of the integer vector defining the auxiliary pairing. Next, we observe that degenerate auxiliary pairings expect to make modified EI harder. We provide a sufficient condition on the integer vector, in terms of its max norm, so that the corresponding auxiliary paring is non-degenerate. Finally, we define an infinite set of curve parameters, which includes those of typical pairing friendly curves, and we show that, within those parameters, PI of arbitrarily given generalized ate pairing can be reduced to modified EI in polynomial time.}, booktitle={Pairing-Based Cryptography – Pairing 2013}, publisher={Springer International Publishing}, author={Chang, Seunghwan and Hong, Hoon and Lee, Eunjeong and Lee, Hyang-Sook}, year={2014}, pages={77–96} } @inproceedings{eraşcu_hong_2014, place={New York, NY, USA}, title={Synthesis of Optimal Numerical Algorithms Using Real Quantifier Elimination (Case Study: Square Root Computation)}, url={https://doi.org/10.1145/2608628.2608654}, DOI={10.1145/2608628.2608654}, abstractNote={We report on on-going efforts to apply real quantifier elimination to the synthesis of optimal numerical algorithms. In particular, we describe a case study on the square root problem: given a real number x and an error bound ε, find a real interval such that it contains [EQUATION] and its width is less than or equal to ε. A typical numerical algorithm starts with an initial interval and repeatedly updates it by applying a "refinement map" on it until it becomes narrow enough. Thus the synthesis amounts to finding a refinement map that ensures the correctness and optimality of the resulting algorithm. This problem can be formulated as a real quantifier elimination. Hence, in principle, the synthesis can be carried out automatically. However, the computational requirement is huge, making the automatic synthesis practically impossible with the current general real quantifier elimination software. We overcame the difficulty by (1) carefully reducing a complicated quantified formula into several simpler ones and (2) automatically eliminating the quantifiers from the resulting ones using the state of the art quantifier elimination software. As the result, we were able to synthesize semi-automatically, under mild assumptions, a class of optimal maps, which are significantly better than the well known hand-crafted Secant-Newton map. Interestingly, the optimal synthesized maps are not contracting as one would naturally expect.}, booktitle={Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation}, publisher={Association for Computing Machinery}, author={Eraşcu, Mădălina and Hong, Hoon}, editor={Nabeshima, Katsusuke and Nagasaka, Kosaku and Winkler, Franz and Szántó, ÁgnesEditors}, year={2014}, pages={162–169} } @article{hong_dongming_jing_2013, title={A framework for improving uniformity of parameterizations of curves}, volume={56}, ISSN={["1869-1919"]}, url={http://dx.doi.org/10.1007/s11432-013-4924-4}, DOI={10.1007/s11432-013-4924-4}, number={10}, journal={SCIENCE CHINA-INFORMATION SCIENCES}, publisher={Springer Science and Business Media LLC}, author={Hong, Hoon and DongMing, Wang and Jing, Yang}, year={2013}, month={Oct} } @inbook{yang_wang_hong_2013, title={Improving Angular Speed Uniformity by C 1 Piecewise Reparameterization}, ISBN={9783642406713 9783642406720}, ISSN={0302-9743 1611-3349}, url={http://dx.doi.org/10.1007/978-3-642-40672-0_3}, DOI={10.1007/978-3-642-40672-0_3}, abstractNote={We show how to compute a C 1 piecewise-rational reparameterization that closely approximates to the arc-angle parameterization of any plane curve by C 1 piecewise Möbius transformation. By making use of the information provided by the first derivative of the angular speed function, the unit interval is partitioned such that the obtained reparameterization has high uniformity and continuous angular speed. An iteration process is used to refine the interval partition. Experimental results are presented to show the performance of the proposed method and the geometric behavior of the computed reparameterizations.}, booktitle={Automated Deduction in Geometry}, publisher={Springer Berlin Heidelberg}, author={Yang, Jing and Wang, Dongming and Hong, Hoon}, year={2013}, pages={33–47} } @article{yang_wang_hong_2013, title={Improving angular speed uniformity by reparameterization}, volume={30}, url={http://dx.doi.org/10.1016/j.cagd.2013.04.001}, DOI={10.1016/j.cagd.2013.04.001}, abstractNote={We introduce the notion of angular speed uniformity as a quality measure for parameter-izations of plane curves and propose an algorithm to compute uniform reparameterizations for quadratic and cubic curves. We prove that only straight lines have uniform rational parameterizations. For any plane curve other than lines, we show how to find a rational reparameterization that has the maximum uniformity among all the rational parameterizations of the same degree. We also establish specific results for quadratic and certain cubic Bézier curves.}, number={7}, journal={Computer Aided Geometric Design}, publisher={Elsevier BV}, author={Yang, Jing and Wang, Dongming and Hong, Hoon}, year={2013}, month={Oct}, pages={636–652} } @article{burdis_kogan_hong_2013, title={Object-Image Correspondence for Algebraic Curves under Projections}, volume={9}, ISSN={["1815-0659"]}, url={http://dx.doi.org/10.3842/sigma.2013.023}, DOI={10.3842/sigma.2013.023}, abstractNote={We present a novel algorithm for deciding whether a given planar curve is an image of a given spatial curve, obtained by a central or a parallel projection with unknown parameters.The motivation comes from the problem of establishing a correspondence between an object and an image, taken by a camera with unknown position and parameters.A straightforward approach to this problem consists of setting up a system of conditions on the projection parameters and then checking whether or not this system has a solution.The computational advantage of the algorithm presented here, in comparison to algorithms based on the straightforward approach, lies in a significant reduction of a number of real parameters that need to be eliminated in order to establish existence or non-existence of a projection that maps a given spatial curve to a given planar curve.Our algorithm is based on projection criteria that reduce the projection problem to a certain modification of the equivalence problem of planar curves under affine and projective transformations.To solve the latter problem we make an algebraic adaptation of signature construction that has been used to solve the equivalence problems for smooth curves.We introduce a notion of a classifying set of rational differential invariants and produce explicit formulas for such invariants for the actions of the projective and the affine groups on the plane.}, journal={SYMMETRY INTEGRABILITY AND GEOMETRY-METHODS AND APPLICATIONS}, publisher={SIGMA (Symmetry, Integrability and Geometry: Methods and Application)}, author={Burdis, Joseph M. and Kogan, Irina A. and Hong, Hoon}, year={2013} } @inproceedings{chang_hong_lee_lee_2013, title={Pairing Inversion via Non-degenerate Auxiliary Pairings}, volume={8365}, url={https://doi.org/10.1007/978-3-319-04873-4\_5}, DOI={10.1007/978-3-319-04873-4\_5}, booktitle={Pairing-Based Cryptography - Pairing 2013 - 6th International Conference, Beijing, China, November 22-24, 2013, Revised Selected Papers}, publisher={Springer}, author={Chang, Seunghwan and Hong, Hoon and Lee, Eunjeong and Lee, Hyang-Sook}, editor={Cao, Zhenfu and Zhang, FangguoEditors}, year={2013}, pages={77–96} } @article{chang_hong_lee_lee_2013, title={Reducing Pairing Inversion to Exponentiation Inversion using Non-degenerate Auxiliary Pairing}, volume={2013}, url={http://eprint.iacr.org/2013/313}, journal={IACR Cryptol. ePrint Arch.}, author={Chang, Seunghwan and Hong, Hoon and Lee, Eunjeong and Lee, Hyang-Sook}, year={2013}, pages={313} } @article{hong_lee_lee_park_2013, title={Simple and exact formula for minimum loop length in Ate (i) pairing based on Brezing-Weng curves}, volume={67}, ISSN={["0925-1022"]}, url={http://dx.doi.org/10.1007/s10623-011-9605-y}, DOI={10.1007/s10623-011-9605-y}, abstractNote={We provide a simple and exact formula for the minimum Miller loop length in Ate i pairing based on Brezing–Weng curves, in terms of the involved parameters, under a mild condition on the parameters. It will also be shown that almost all cryptographically useful/meaningful parameters satisfy the mild condition. Hence the simple and exact formula is valid for them. It will also turn out that the formula depends only on essentially two parameters, providing freedom to choose the other parameters to address the design issues other than minimizing the loop length.}, number={2}, journal={DESIGNS CODES AND CRYPTOGRAPHY}, publisher={Springer Science and Business Media LLC}, author={Hong, Hoon and Lee, Eunjeong and Lee, Hyang-Sook and Park, Cheol-Min}, year={2013}, month={May}, pages={271–292} } @article{erascu_hong_2013, title={The Secant-Newton Map is Optimal Among Contracting Quadratic Maps for Square Root Computation}, volume={18}, url={http://interval.louisiana.edu/reliable-computing-journal/volume-18/reliable-computing-18-pp-073-081.pdf}, journal={Reliab. Comput.}, author={Erascu, Madalina and Hong, Hoon}, year={2013}, pages={73–81} } @inbook{yang_wang_hong_2012, title={Improving Angular Speed Uniformity by Optimal C 0 Piecewise Reparameterization}, ISBN={9783642329722 9783642329739}, ISSN={0302-9743 1611-3349}, url={http://dx.doi.org/10.1007/978-3-642-32973-9_29}, DOI={10.1007/978-3-642-32973-9_29}, abstractNote={We adapt the C 0 piecewise Möbius transformation to compute a C 0 piecewise-rational reparameterization of any plane curve that approximates to the arc-angle parameterization of the curve. The method proposed on the basis of this transformation can achieve highly accurate approximation to the arc-angle parameterization. A mechanism is developed to optimize the transformation using locally optimal partitioning of the unit interval. Experimental results are provided to show the effectiveness and efficiency of the reparameterization method.}, booktitle={Computer Algebra in Scientific Computing}, publisher={Springer Berlin Heidelberg}, author={Yang, Jing and Wang, Dongming and Hong, Hoon}, year={2012}, pages={349–360} } @inproceedings{yang_wang_hong_2012, title={Improving Angular Speed Uniformity by Optimal C 0 Piecewise Reparameterization}, volume={7442}, url={https://doi.org/10.1007/978-3-642-32973-9\_29}, DOI={10.1007/978-3-642-32973-9\_29}, booktitle={Computer Algebra in Scientific Computing - 14th International Workshop, CASC 2012, Maribor, Slovenia, September 3-6, 2012. Proceedings}, publisher={Springer}, author={Yang, Jing and Wang, Dongming and Hong, Hoon}, editor={Gerdt, Vladimir P. and Koepf, Wolfram and Mayr, Ernst W. and Vorozhtsov, Evgenii V.Editors}, year={2012}, pages={349–360} } @article{hong_lee_lee_park_2012, title={Maximum gap in (inverse) cyclotomic polynomial}, volume={132}, ISSN={["1096-1658"]}, url={http://dx.doi.org/10.1016/j.jnt.2012.04.008}, DOI={10.1016/j.jnt.2012.04.008}, abstractNote={Let g(f) denote the maximum of the differences (gaps) between two consecutive exponents occurring in a polynomial f. Let Φn denote the n-th cyclotomic polynomial and let Ψn denote the n-th inverse cyclotomic polynomial. In this note, we study g(Φn) and g(Ψn) where n is a product of odd primes, say p1r-dimensional Euclidean space into regions over which a given set of polynomials have constant signs. An important component of the CAD method is the projection operation: given a set A of r-variate polynomials, the projection operation produces a set P of (r - 1)-variate polynomials such that a CAD of r-dimensional space for A can be constructed from a CAD of (r-1)-dimensional space for P. In this paper, we present an improvement to the projection operation. By generalizing a lemma on which the proof of the original projection operation is based, we are able to find another projection operation which produces a smaller number of polynomials. Let m be the number of polynomials contained in A, and let n be a bound for the degree of each polynomial in A in the projection variable. The number of polynomials produced by the original projection operation is dominated by m2n3 whereas the number of polynomials produced by our projection operation is dominated by m2n2.}, booktitle={Proceedings of the international symposium on Symbolic and algebraic computation - ISSAC '90}, publisher={ACM Press}, author={Hong, H.}, year={1990} }