ScholarBank@NUShttps://scholarbank.nus.edu.sgThe DSpace digital repository system captures, stores, indexes, preserves, and distributes digital research material.Tue, 15 Oct 2019 22:02:16 GMT2019-10-15T22:02:16Z50221- Fast computation of the Bezout and Dixon resultant matriceshttps://scholarbank.nus.edu.sg/handle/10635/39280Title: Fast computation of the Bezout and Dixon resultant matrices
Authors: Chionh, E.-W.; Zhang, M.; Goldman, R.N.
Abstract: Efficient algorithms are derived for computing the entries of the Bezout resultant matrix for two univariate polynomials of degree n and for calculating the entries of the Dixon-Cayley resultant matrix for three bivariate polynomials of bidegree (m, n). Standard methods based on explicit formulas require O(n3) additions and multiplications to compute all the entries of the Bezout resultant matrix. Here we present a new recursive algorithm for computing these entries that uses only O(n2) additions and multiplications. The improvement is even more dramatic in the bivariate setting. Established techniques based on explicit formulas require O(m4n4) additions and multiplications to calculate all the entries of the Dixon-Cayley resultant matrix. In contrast, our recursive algorithm for computing these entries uses only O(m2n3) additions and multiplications. © 2002 Academic Press.
Tue, 01 Jan 2002 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/392802002-01-01T00:00:00Z
- Proper reparametrization for inherently improper unirational varietieshttps://scholarbank.nus.edu.sg/handle/10635/39659Title: Proper reparametrization for inherently improper unirational varieties
Authors: Shen, L.; Chionh, E.; Gao, X.-S.; Li, J.
Abstract: In this paper, a class of lattice supports in the lattice space Z m is found to be inherently improper because any rational parametrization from C m to C n defined on such a support is improper. The improper index for such a lattice support is defined to be the gcd of the normalized volumes of all the simplex sub-supports. The structure of an improper support S is analyzed and shrinking transformations are constructed to transform S to a proper one. For a generic rational parametrization RP defined on an improper support S, we prove that its improper index is the improper index of S and give a proper reparametrization algorithm for RP. Finally, properties for rational parametrizations defined on an improper support and with numerical coefficients are also considered. © 2011 Institute of Systems Science, Academy of Mathematics and Systems Science, CAS and Springer-Verlag Berlin Heidelberg.
Sat, 01 Jan 2011 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/396592011-01-01T00:00:00Z
- On a relationship between the moving line and moving conic coefficient matriceshttps://scholarbank.nus.edu.sg/handle/10635/39123Title: On a relationship between the moving line and moving conic coefficient matrices
Authors: Zhang, M.; Chionh, E.-W.; Goldman, R.N.
Abstract: The method of moving curves and moving surfaces is a new, effective tool for implicitizing rational curves and surfaces. Here we investigate a relationship between the moving line coefficient matrix and the moving conic coefficient matrix for rational curves. Based on this relationship, we present a new proof that the method of moving conics always produces the implicit equation of a rational curve when there are no low degree moving lines that follow the curve.
Fri, 01 Jan 1999 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/391231999-01-01T00:00:00Z
- Corner edge cutting and Dixon A-resultant quotientshttps://scholarbank.nus.edu.sg/handle/10635/39198Title: Corner edge cutting and Dixon A-resultant quotients
Authors: Foo, M.-C.; Chionh, E.-W.
Abstract: The classical Dixon resultant formulation gives the exact A-resultant for the bi-degree rectangular monomial support. But the formulation gives a multiple of the A-resultant when the monomial support is a bi-degree rectangular support with some corner edges removed. Fortunately, here the extraneous factors can be easily identified a priori and the A-resultant can be expressed explicitly as a quotient: the determinant of a Dixon matrix divided by a product of brackets. All proofs in the paper are constructive. One of the proofs is mechanically done by a Maple program. © 2003 Elsevier Ltd. All rights reserved.
Thu, 01 Jan 2004 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/391982004-01-01T00:00:00Z
- Inherently improper surface parametric supportshttps://scholarbank.nus.edu.sg/handle/10635/39576Title: Inherently improper surface parametric supports
Authors: Chionh, E.-W.; Gao, X.-S.; Shen, L.-Y.
Abstract: We identify a class of monomial supports that are inherently improper because any surface rational parametrization defined on them is improper. A surface support is inherently improper if and only if the gcd of the normalized areas of the triangular sub-supports is non-unity. The constructive proof of this claim can be used to detect all and correct almost all improper surface parametrizations due to improper supports. © 2006 Elsevier B.V. All rights reserved.
Sun, 01 Jan 2006 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/395762006-01-01T00:00:00Z
- Shifting planes always implicitize a surface of revolutionhttps://scholarbank.nus.edu.sg/handle/10635/39780Title: Shifting planes always implicitize a surface of revolution
Authors: Chionh, E.-W.
Abstract: A degree n rational plane curve revolving in space around an axis in its plane yields a degree 2n rational surface. Two formulas are presented to generate 2n moving planes that follow the surface. These 2n moving planes give a 2 n × 2 n implicitization determinant that manifests conspicuously the geometric action of revolution in two algebraic aspects. Firstly the moving planes are constructed by successively shifting terms of polynomials from one column to another of a spawning 3 × 3 determinant. Secondly the right half of the 2 n × 2 n implicitization determinant is an n-row rotation of the left half with some sign flipping. Additionally, it is observed that rational parametrizations for a surface obtained as a surface of revolution with a symmetric generatrix must be improper. © 2009 Elsevier B.V. All rights reserved.
Thu, 01 Jan 2009 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/397802009-01-01T00:00:00Z
- Using multivariate resultants to find the intersection of three quadric surfaceshttps://scholarbank.nus.edu.sg/handle/10635/99459Title: Using multivariate resultants to find the intersection of three quadric surfaces
Authors: Chionh, Eng-Wee; Goldman, Ronald N.; Miller, James R.
Abstract: Macaulay's concise but explicit expression for multivariate resultants has many potential applications in computer-aided geometric design. Here we describe its use in solid modeling for finding the intersections of three implicit quadric surfaces. By Bezout's theorem, three quadric surfaces have either at most eight or infinitely many intersections. Our method finds the intersections, when there are finitely many, by generating a polynomial of degree at most eight whose roots are the intersection coordinates along an appropriate axis. Only addition, subtraction, and multiplication are required to find the polynomial. But when there are possibilities of extraneous roots, division and greatest common divisor computations are necessary to identify and remove them.
Tue, 01 Oct 1991 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/994591991-10-01T00:00:00Z
- 0/0 Simplifies implicitizationhttps://scholarbank.nus.edu.sg/handle/10635/39538Title: 0/0 Simplifies implicitization
Authors: Chionh, E.-W.
Abstract: A base point of a surface rational parametrization maps to an indeterminate surface point (0/0,0/0,0/0). A quotient resultant becomes indeterminate when it specializes to 0/0. These double anomalies seem hazardous to implicitization. But surprisingly, when they do happen simultaneously, the implicitization result may become simpler. This desirable situation arises when base points are due to a corner-cut parametric monomial support and the corresponding quotient resultant is indeterminate due to the collinearity of corner control vertices. The simplification effect is quite substantial: the implicit polynomial is an a priori known maximal minor from the numerator determinant of the quotient resultant, consequently not only the implicitization determinant is shrunk but division is avoided altogether. © 2007 Elsevier Ltd. All rights reserved.
Tue, 01 Jan 2008 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/395382008-01-01T00:00:00Z
- Rectangular Corner Cutting and Dixon A-resultantshttps://scholarbank.nus.edu.sg/handle/10635/39888Title: Rectangular Corner Cutting and Dixon A-resultants
Authors: Chionh, E.-W.
Abstract: The classical Dixon resultant for three bi-degree polynomials in two variables is an A-resultant with a rectangular bi-degree monomial support. This paper shows that the determinant of the Dixon coefficient matrix persists as an A-resultant after rectangular corner cutting, that is, the removal of one or more rectangular sub-supports at the corners of the bi-degree support. The proof is constructive and produces intermediate results which are significant in their own right. © 2001 Academic Press.
Mon, 01 Jan 2001 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/398882001-01-01T00:00:00Z
- Parallel Dixon matrices by brackethttps://scholarbank.nus.edu.sg/handle/10635/39889Title: Parallel Dixon matrices by bracket
Authors: Chionh, E.-W.
Abstract: It is known that the Dixon matrix can be constructed in parallel either by entry or by diagonal. This paper presents another parallel matrix construction, this time by bracket. The parallel by bracket algorithm is the fastest among the three, but not surprisingly it requires the highest number of processors. The method also shows analytically that the Dixon matrix has a total of m(m + 1)2(m + 2)n(n + 1)2(n + 2)/36 brackets but only mn(m + 1)(n + 1)(mn + 2m + 2n + 1)/6 of them are distinct.
Wed, 01 Jan 2003 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/398892003-01-01T00:00:00Z
- Elimination and resultants. Part 2: Multivariate resultantshttps://scholarbank.nus.edu.sg/handle/10635/99265Title: Elimination and resultants. Part 2: Multivariate resultants
Authors: Wee, Chionh Eng; Goldman, Ronald N.
Abstract: Multivariate resultant expressions which are resultants for systems of three or more equations are described. The dialytic method produces the Sylvester bivariate resultant but it yields multiples of multivariate resultants in which extraneous factors must be identified and discarded to obtain the resultant. Generally, multivariate resultants must be expressed as quotients of two determinants. Also discussed are Dixon bidegree resultants for three bidegree equations and several resultant expressions for three equal degree equations. The Macaulay quotient is explained, together with a description of the μ-resultant.
Wed, 01 Mar 1995 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/992651995-03-01T00:00:00Z
- On the minors of the implicitization Bezout matrix for a rational plane curvehttps://scholarbank.nus.edu.sg/handle/10635/39047Title: On the minors of the implicitization Bezout matrix for a rational plane curve
Authors: Chionh, E.-W.; Sederberg, T.W.
Abstract: This paper investigates the first minors Mi,j of the Bezout matrix used to implicitize a degree-n plane rational curve P(t). It is shown that the degree n-1 curve Mi,j = 0 passes through all of the singular points of P(t). Furthermore, the only additional points at which Mi,j = 0 and P(t) intersect are an (i+j)-fold intersection at P(0) and a (2n-2-i-j)-fold intersection at P(∞). Thus, a polynomial whose roots are exactly the parameter values of the singular points of P(t) can be obtained by intersecting P(t) with M0,0. Previous algorithms of finding such a polynomial are less direct. We further show that Mi,j = Mk,l if i+j = k+l. The method also clarifies the applicability of inversion formulas and yields simple checks for the existence of singularities in a cubic Be&acute;zier curve.
Mon, 01 Jan 2001 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/390472001-01-01T00:00:00Z
- Concise parallel Dixon determinanthttps://scholarbank.nus.edu.sg/handle/10635/99224Title: Concise parallel Dixon determinant
Authors: Chionh, E.-W.
Abstract: The Dixon resultant is an important computational tool in CAGD. Its definition is theoretically elegant but computationally clumsy due to enormous intermediate expression swell. To speed up the computation, a new Dixon determinant entry formula is derived The entry formula not only enables the Dixon determinant entries to be computed in parallel, it also solves the problem of intermediate expression swell. Furthermore, the entry formula leads to an expression counting the number of 3 × 3 determinants in the Dixon determinant. © 1997 Elsevier Science B.V.
Fri, 01 Aug 1997 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/992241997-08-01T00:00:00Z
- On the existence and the coefficients of the implicit equation of rational surfaceshttps://scholarbank.nus.edu.sg/handle/10635/99363Title: On the existence and the coefficients of the implicit equation of rational surfaces
Authors: Chionh, Eng-Wee; Goldman, Ronald N.
Abstract: The existence of the implicit equation means every rational surface is a subset of an irreducible algebraic surface. The subset relation can be proper and this may cause problems in certain applications in computer aided geometric design. This anomaly is illustrated by an examples.
Sat, 01 Jan 1994 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/993631994-01-01T00:00:00Z
- Elimination and resultants part 1: elimination and bivariate resultantshttps://scholarbank.nus.edu.sg/handle/10635/99264Title: Elimination and resultants part 1: elimination and bivariate resultants
Authors: Wee, Chionh Eng; Goldman, Ronald N.
Abstract: Elimination theory and resultants are important manipulative tools that contribute theoretical insights and practical algorithms to computer graphics and geometric modeling. In this tutorial, resultant properties are listed to enhance overall understanding of resultants. For bivariate resultants, two explicit expressions are presented: the Sylvester matrix and the Bezout determinants.
Sun, 01 Jan 1995 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/992641995-01-01T00:00:00Z
- Degree, multiplicity, and inversion formulas for rational surfaces using u-resultantshttps://scholarbank.nus.edu.sg/handle/10635/99236Title: Degree, multiplicity, and inversion formulas for rational surfaces using u-resultants
Authors: Chionh, E.-W.; Goldman, R.N.
Abstract: Rational surface patches are popular in computer aided geometric design. But for any given rational parametrization, many questions arise: "Are there base points?", "What is the degree of the surface?", "How to do inversion?", "Is the representation redundant?", "Is a point exceptional?" These and many other problems can be solved in one stroke by using the u-resultant. With a computer algebra system, the implementation of our algorithms is straightforward. A method to speed up the computation is also provided. © 1992.
Mon, 01 Jun 1992 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/992361992-06-01T00:00:00Z
- Using multivariate resultants to find the implicit equation of a rational surfacehttps://scholarbank.nus.edu.sg/handle/10635/99458Title: Using multivariate resultants to find the implicit equation of a rational surface
Authors: Chionh, E.-W.; Goldman, R.N.
Abstract: Given a parametrization of a rational surface, the absence of base points is shown to be a necessary and sufficient condition for the auxiliary resultant to be a power of the implicit polynomial. The method of resultants also reveals other important properties of rational surface representations, including the coefficients of the implicit equation, the relationship between the implicit and parametric degrees, the degree of each coordinate variable of the implicit equation, and the number of correspondence of the parametrization. © 1992 Springer-Verlag.
Fri, 01 May 1992 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/994581992-05-01T00:00:00Z
- The maximality of the dixon matrix on corner-cut monomial supportshttps://scholarbank.nus.edu.sg/handle/10635/42217Title: The maximality of the dixon matrix on corner-cut monomial supports
Authors: Chionh, E.-W.
Abstract: It has been established that the bivariate Dixon matrix persists to be the exact resultant when there are at most two exposed points at each corner of a corner-cut support; but it becomes singular when there are four or more exposed points at any of the corners. For the remaining case of three or fewer exposed points at each of the corners, it is observed that the Dixon matrix is maximal but its determinant is a multiple of the resultant with a priori known bracket powers as the extraneous factors. The maximality of the Dixon matrix for the three-or-fewer exposed points case has been established mechanically for the special situation in which the excess degree is unity when there are three exposed points at a corner. This paper presents a greatly simplified mechanical proof so that its validity can be easily verified. © 2008 Springer-Verlag Berlin Heidelberg.
Tue, 01 Jan 2008 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/422172008-01-01T00:00:00Z
- Surface-surface intersection by hermite interpolationhttps://scholarbank.nus.edu.sg/handle/10635/42216Title: Surface-surface intersection by hermite interpolation
Authors: Chionh, E.-W.
Abstract: A fast heuristic to approximate the intersection curve of two surface patches was originally proposed by Sederberg and Nishita. The patches are rationally parametrized and they cut each other transversely. This paper reports a simple generalization that greatly improves the accuracy of the original heuristic. The generalization either avoids or attenuates the approximation error. Avoidance is achieved when the improved heuristic produces the exact intersection curve; attenuation is accomplished with an aggregate square distance formula guiding the selection of a generalized constraint for a better fit.
Tue, 01 Jan 2008 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/422162008-01-01T00:00:00Z
- Formal power series and loose entry formulas for the Dixon matrixhttps://scholarbank.nus.edu.sg/handle/10635/39933Title: Formal power series and loose entry formulas for the Dixon matrix
Authors: Xiao, W.; Chionh, E.-W.
Abstract: Formal power series are used to derive four entry formulas for the Dixon matrix. These entry formulas have uniform and simple summation bounds for the entire Dixon matrix. When corner cutting is applied to the monomial support, each of the four loose entry formulas simplifies greatly for some rows and columns associated with a particular corner, but still maintains the uniform and simple summation bounds. Uniform summation bounds make the entry formulas loose because redundant brackets that eventually vanish are produced. On the other hand, uniform summation bounds reveal valuable information about the properties of the Dixon matrix for a corner-cut monomial support. © Springer-Verlag Berlin Heidelberg 2005.
Sat, 01 Jan 2005 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/399332005-01-01T00:00:00Z
- Shifting planes to follow a surface of revolutionhttps://scholarbank.nus.edu.sg/handle/10635/39992Title: Shifting planes to follow a surface of revolution
Authors: Chionh, E.-W.
Abstract: A degree n rational plane curve rotating about an axis in the plane creates a degree 2n rational surface. Two formulas are given to generate 2n moving planes that follow the surface. These 2n moving planes lead to a 2n×2n implicitization determinant that manifests the geometric revolution algebraically in two aspects. Firstly the moving planes are constructed by successively shifting terms of polynomials from one column to another of a spawning 3×3 determinant. Secondly the right half of the 2n×2n implicitization determinant is almost an n-row rotation of the left half. As an aside, it is observed that rational parametrizations of a surface of revolution due to a symmetric rational generatrix must be improper. © 2008 Springer-Verlag Berlin Heidelberg.
Tue, 01 Jan 2008 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/399922008-01-01T00:00:00Z
- Bracket producing rows and columns of the dixon determinanthttps://scholarbank.nus.edu.sg/handle/10635/40058Title: Bracket producing rows and columns of the dixon determinant
Authors: Xiao, W.; Chionh, E.-W.
Abstract: The Dixon resultant for a bivariate polynomial system has many interesting properties. When the unmixed canonical bidegree monomial support of the polynomial system undergoes corner cutting, some monomial points become distinguished by being exposed. When a corner has exactly three exposed monomial points, certain rows and columns of the Dixon matrix, called almost-exposed rows and columns, will produce a factor which is a power of the bracket corresponding to the three exposed points. The power is determined by the relative positions of these three exposed points. This observation is very useful when constructing quotient Dixon resultants. © 2006 IEEE.
Mon, 01 Jan 2007 00:00:00 GMThttps://scholarbank.nus.edu.sg/handle/10635/400582007-01-01T00:00:00Z