> <\body> <\session|mathemagix|default> <\textput> |<\doc-author-data|> \; GALAAD, INRIA Sophia Antipolis Email: lbathang@sophia.inria.fr >> Computing the intersection between algebraic varieties is a fundamental task in Computer Aided Geometric Design. Several methods and approaches have been developed for that purpose. Some of them are based on matrix representations of the objects that allow to transform the computation of the intersection locus into generalized eigencomputations . The aim of our works is to compute the matrix representation of these objects and to show that similar algorithms can be implemented even if the matrix representation used are non square matrices. Notice that recent researches, known under the name of the >-basis method>, have demonstrated that these non square representation matrices are much easier to compute than square representation matrices. In particular, the matrix representation of rational space curves are always non-square matrices \; The approach to the curve/curve, curve/surface intersection problem that we develop in our works contain two main parts. The first one is the computation of a matrix representation of the curve and surface from theirs parametrization. This work requires advanced concepts of commutative algebra and algebraic Geometry such as: Elimination theory, free resolution of modules, Koszul complex, approximate complex, Fitting invariant, MacRae invariant, algebraic variety, primary decomposition of ideal,....One of the most effective algorithm for computing them is via Grobner basis of modules, Grobner basis of ideals or via >-basis of a set polynomial. All of this computings are symbolic computations. \; After combining this matrix representation of the curve and the surface with the parameterization of the curve, the second part consists of a matrix reduction and some eigenvalue computations. In this part, we use the technics of linear algebra such as: Kronecker form of a pencil matrix, Smith form of univariate polynomial matrix, LU-decomposition, QR-decomposition, Sylvester matrix, Bezout matrix,.... As a particularity of our method, these two parts can be performed either by symbolic exact computations or by numerical approached computations. However, it seems that a good combination is to choose a symbolic treatment for the first part, so that the change of representation does not affect the intersection locus, and then using numerical computations, typically LU-decompositions, QR-decomposition and eigenvalues computations, to end the algorithm. \; We develop this package in order to solve all problems which we talk above. Hereafter, we introduce some functions for explaining the work which we make. \; Mathemagix: Package: Algebramix (Symbolic Computation). Packages: Realroot, Numerix, Linalg (Numeric Computation).\ \; \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ ||>|-basis and Koszul map>>||>>>> \; <\textput> >-basis of a set polynomials> Given the set of homogeneous polynomial:=,f,...,f|)>> of the same degree 1> in > with ,...,f|)>=1>.\ \; \ \ \ \ \ \ \ \ \ \ \ \ |)>>:=,g,...,g|)>\\:f+...+gf=0>>|}> >.\ \; By Hilbert-Burch Theorem: >)> is and >-module of rank n. Chosing a basis , u ,...,u> of |)>>. <\definition> , u ,...,u> is called a >-basis> of >. <\remark> Given the set of univariate polynomial :=,f,...,f|)>> in > with n:=max (deg )\1> and \ ,...,f|)>=1>. Homogenizing \ ,i=0,1,\,n> by new variable t which are denoted > such that > are homogeneous polynomial in K[s,t] of the same degree n. We chose a basis , u ,...,u> of Syz >. Then, the set , u,\,u> is called a >-basis of the set univariate polynomial>. <\em> \; gives the >-basis> of the set of univariate polynomial >. <\em> gives the >-basis> of the set of homegenous polynomial> with homogeneous variable var. <\textput> <\example> :=, -3*x+3*x,x+1,x+1|)>>.\ Then > -basis of > is <\input> <|input> include "shape/matrixrepresentation/mubase.mmx" <\input> <|input> a1:=polynomial(0,0,3);a2:=polynomial(0,3,0,-3); a3:=polynomial(1,1); a4:=polynomial(1,0,1); <\unfolded-io> <|unfolded-io> f:=[a1,a2,a3,a4] <|unfolded-io> ,-3*x+3*x,x+1,x+1|]>> <\unfolded-io> <|unfolded-io> mubase f <|unfolded-io> *x-|0|-1|x+1>>>|]>,>>|]>,>>|]>|]>> <\input> <|input> c1:=polynomial(-33,115/2,-49/2,0,1); c2:=polynomial(-36,61,-25,0,1); c3:=polynomial(-8,27/2,-13/2,1);c4:=polynomial(1); <\unfolded-io> <|unfolded-io> f:=[c1,c2,c3,c4] <|unfolded-io> -*x+*x-33,x-25*x+61*x-36,x-*x+*x-8,1|]>> <\unfolded-io> <|unfolded-io> mubase f <|unfolded-io> *x-*x+3>>>|]>,|1|*x-|*x+>>>|]>,*x-|*x+|*x-|*x->>>|]>|]>> <\input> <|input> f0:=QQ['x]\\"x^3+x+1"; f1:=QQ['x]\\"x^4-x+2";f2:=QQ['x]\\"x^6-2*x-1"; <\unfolded-io> <|unfolded-io> f:=[f0,f1,f2] <|unfolded-io> +x+1,x-x+2,x-2*x-1|]>> <\unfolded-io> <|unfolded-io> mubase f <|unfolded-io> +4*x-*x+4|*x+*x-4*x-|*x->>>|]>,*x-*x+*x-|*x-*x+*x+|*x+>>>|]>|]>> \; <\textput> <\example> :=+x*y+y, x-x*y,x+x*y+x*y|)>>.\ Then > -basis of > is: <\input> <|input> f0:=QQ['x,'y]\\"x^3+x*y^2+y^3"; f1:=QQ['x,'y]\\"x^3-x^2*y";\ f2:=QQ['x,'y]\\"x^3+x^2*y+x*y^2"; varf1:=QQ['x,'y]\\"x"; varf2:=QQ['x,'y]\\"y"; <\unfolded-io> <|unfolded-io> f:=[f0,f1,f2] <|unfolded-io> +x*y+y,x-x*y,x+x*y+x*y|]>> <\unfolded-io> <|unfolded-io> mubase_homogeneous(f,[varf1,varf2]) <|unfolded-io> +x*y|-x+y|-x-x*y-y>>>|]>,*x|*x|*y>>>|]>|]>> \; <\textput> Let ,f,\,f> be homogeneous polynomials in > of the same degree 1> such that ||gcd,f,\,f|)>\\|{>0|}>>. Consider the regular map <\eqnarray*> \ \ \ \ \ \ \ \ : \ \ \>>|>|>>>|>|>|:f:\:f|)>.>>>> \ Algebraic curve > := Image of > \ which is called a > curve.\ <\definition> A matrix |)>> with entries in ,x,\.,x|]>> is said to be >>>> if\ <\itemize-dot> |)>> is generically full rank, The rank of |)>> drops exactly on the curve >>>. Now, we give some example to compute the matrix representation of a parameterized curve. We focus on curve in >> and >> because they are the most interesting cases. <\with|color|blue> Function: matrix_rep_curve_plane_homogeneous(curplane,varcur,varimplcurve). Function: matrix_rep_curve_plane(curplane,varimplcurve). Function: matrix_rep_curve_space_homogeneous(curspace,varcur,varimplcurve). Function: matrix_rep_curve_space(curspace,varimplcurve). <\example> |)>: f=s+t, f=s*t, f=s+s*t+t >.\ Then a matrix representation of > is <\input> <|input> include "shape/matrixrepresentation/curvesurface.mmx" <\input> <|input> R:=QQ['s,'t,'x,'y,'z,'w]; <\unfolded-io> <|unfolded-io> curplane:=[R\\"s^3+t^3",R\\"s^2*t",R\\"s^3+s*t^2+t^3"] <|unfolded-io> +t,s*t,s+s*t+t|]>> <\unfolded-io> <|unfolded-io> varcur:=[R\\"s",R\\"t"] <|unfolded-io> > <\unfolded-io> <|unfolded-io> varimplcurve:=[R\\"x",R\\"y",R\\"z"] <|unfolded-io> > <\unfolded-io> <|unfolded-io> matrix_rep_curve_plane_homogeneous(curplane,varcur,varimplcurve) <|unfolded-io> ||>>|]>> <\unfolded-io> <|unfolded-io> curplane:=[polynomial(1,0,0,1), polynomial(0,0,1),polynomial(1,1,0,1)] <|unfolded-io> +1,x,x+x+1|]>> <\unfolded-io> <|unfolded-io> matrix_rep_curve_plane(curplane,varimplcurve) <|unfolded-io> ||>>|]>> <\textput> <\example> \ |)>: f=3*s*t, f=-3*s+3*s**t, f=s*t+t, f=t >.\ Then a matrix representation of > is <\unfolded-io> <|unfolded-io> curspace:=[R\\"3*s^2*t",R\\"-3*s^3+3*s*t^2",R\\"s*t^2+t^3",R\\"t^3"] <|unfolded-io> *t,-3*s+3*s*t,s*t+t,t|]>> <\unfolded-io> <|unfolded-io> varimplcurspace:=[R\\"x",R\\"y",R\\"z",R\\"w"] <|unfolded-io> > <\unfolded-io> <|unfolded-io> matrix_rep_curve_space_homogeneous(curspace,varcur,varimplcurspace) <|unfolded-io> |>>|]>> <\textput> <\example> |)>: f=3*x*, f=-3*x+3*x*, f=x*+1, f=1 >\ Then a matrix representation of > is <\unfolded-io> <|unfolded-io> curspace:=[polynomial(0,0,3),polynomial(0,3,0,-3),polynomial(1,1), \ \ \ \ \ \ \ \ \ \ \ polynomial(1)] <|unfolded-io> ,-3*x+3*x,x+1,1|]>> <\unfolded-io> <|unfolded-io> matrix_rep_curve_space(curspace,varimplcurspace) <|unfolded-io> |>>|]>> Suppose given a parametrization <\eqnarray*> \ \ \ \ \ \ \ \ : \ \ \>>|>|>>>|>|>|:f:f:f|)>>>>> of a surface > such that ,\,f|)>\\\>.\ <\definition> A matrix |)>> with entries in ,y,z,w|]>> is said to be >>>> if\ <\itemize-dot> |)>> is generically full rank, The rank of |)>> drops exactly on the surface >>>. <\textput> <\example> Steine's Roman Surface |)>: \ f=x+y+z, f=x*y, f=x*z, f=y*z >. Then a matrix representation of > is <\textput> <\input> <|input> include "shape/matrixrepresentation/curvesurface.mmx" <\input> <|input> R:=QQ['x,'y,'z,'w]; <\unfolded-io> <|unfolded-io> Steine:=[R\\"x^2+y^2+z^2",R\\"x*y",R\\"x*z",R\\"y*z"] <|unfolded-io> +y+z,x*y,x*z,y*z|]>> <\unfolded-io> <|unfolded-io> varimplsur:=[R\\"x",R\\"y",R\\"z",R\\"w"] <|unfolded-io> > <\unfolded-io> <|unfolded-io> varsur:=[R\\"x",R\\"y",R\\"z"] <|unfolded-io> > <\unfolded-io> <|unfolded-io> matrix_rep_surface(Steine,varsur,varimplsur) <|unfolded-io> |||||>>|]>> <\textput> <\example> A sphere |)>>:=x+y+z, f=2*x*z,f=2*x*y, f=x-y-z>. Then a matrix representation of is <\unfolded-io> <|unfolded-io> Sphere:=[R\\"x^2+y^2+z^2",R\\"2*x*z",R\\"2*x*y",R\\"x^2-y^2-z^2"] <|unfolded-io> +y+z,2*x*z,2*x*y,x-y-z|]>> <\unfolded-io> <|unfolded-io> matrix_rep_surface(Sphere,varsur,varimplsur) <|unfolded-io> |||||>>|]>> <\input> <|input> \; \; <\textput> Let and be two matrices of size n>. We will call a of A and B a value in the set <\equation*> \:=:rank \min|}>. Suppose given an n>-matrix =|)>> with polynomial entries \\>. It can be equivalently written as a polynomial in with coefficients n>-matrices with entries in >: if |)>|}>> then <\equation*> M=Mt+Mt+\+M where \\n>>. <\definition> The A, B of the matrix M(t) are the matrices with entries in > of size m+n|)>\dm> that are given by \; <\equation*> A=|||>|>||||>|>>|>|>|>|>|>|||>||>|>|>>|>|>|>>>>> <\equation*> \; <\equation*> || >|>|>||||>|>|>||>|>|>>|>|>|>||>|||>||>>>>>>> where I stands for the identity matrix and > stand for the transpose of the matrice ,i=0,1,\,d>. gives the list of matrices: ,M,\.,M|]>>. gives the matrix A. gives the matrix B. <\example> M=>|+3*x>>||>|+x>|+x>>>>>>.\ Then ,\,M \ >and the generalized companion matrices of M are <\input> <|input> include "shape/matrixrepresentation/pencilregular.mmx" <\unfolded-io> <|unfolded-io> M:=matrix(polynomial(0,0,3),polynomial(0,3,0,-3);polynomial(1,1), \ \ \ \ \ \ \ \ \ \ polynomial(1);polynomial(0,1,2), polynomial(0,1,1)) <|unfolded-io> |-3*x+3*x>||+x|x+x>>>|]>> <\unfolded-io> <|unfolded-io> degree M <|unfolded-io> <\unfolded-io> <|unfolded-io> list_coefficients_matrix M <|unfolded-io> ||>>|]>,||>>|]>,||>>|]>,||>>|]>|]>> \; <\unfolded-io> <|unfolded-io> firstcompanionmatrix M <|unfolded-io> |||||||>>|]>> <\unfolded-io> <|unfolded-io> secondcompanionmatrix M <|unfolded-io> |||||||>>|]>> <\input> <|input> \; \; <\textput> <\theorem> drops \ rank drops\ rank-tB|)> drops. \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ > <\definition> Pencil matrices -tB> is called to be regular pencil matrices if A',B' are square matrices and B' is invertible. > gives (A',B'). > gives the list of generalized eigenvalues of M(t).> <\textput> <\example> M=>|+3*x>>||>|+x>|+x>>>>>>.\ Regular pencil matrices (A',B') \ of M and generalized eigenvalues of M are:\ <\input> <|input> include "shape/matrixrepresentation/pencilregular.mmx" <\unfolded-io> <|unfolded-io> M:=matrix(polynomial(0,0,3),polynomial(0,3,0,-3);polynomial(1,1), \ \ \ \ \ \ \ \ \ \ polynomial(1); polynomial(0,1,2), polynomial(0,1,1)) <|unfolded-io> |-3*x+3*x>||+x|x+x>>>|]>> <\unfolded-io> <|unfolded-io> A:=firstcompanionmatrix M <|unfolded-io> |||||||>>|]>> <\unfolded-io> <|unfolded-io> B:=secondcompanionmatrix M <|unfolded-io> |||||||>>|]>> <\unfolded-io> <|unfolded-io> pencilregular(A,B) <|unfolded-io> >>|]>,>>|]>|]>> <\unfolded-io> <|unfolded-io> generalized_eigenvalues M <|unfolded-io> > <\input> <|input> \; <\textput> <\example> \ >|+3*x>|+3*x+2*x+1>>|||+5*x+3*x-1>>||+3*x+1>|+3*x-x+x>>>>>>.\ Then the generalized eigenvalues of M are: <\input> <|input> include "shape/matrixrepresentation/pencilregular.mmx" <\unfolded-io> <|unfolded-io> M:=matrix(polynomial(0,0,3),polynomial(0,3,0,-3),polynomial(1,2,3,4); \ \ \ \ \ \ \ \ \ \ polynomial(1,1),polynomial(1), polynomial(-1,3,0,5,6); \ \ \ \ polynomial(2,1), polynomial(1,3,5), polynomial(0,1,-1,3,4)) <|unfolded-io> |-3*x+3*x|4*x+3*x+2*x+1>|+5*x+3*x-1>|+3*x+1|4*x+3*x-x+x>>>|]>> <\unfolded-io> <|unfolded-io> generalized_eigenvalues M <|unfolded-io> ,-0.65698075043198-0.44590270893738*\,0.024535007283677+0.73173660736968*\,0.024535007283677-0.73173660736968*\,0.23740403501244,-0.12957073012256|]>> <\input> <|input> \; <\textput> <\equation> |)> \ \ \: \ \ \ \ \>\\> \ \ \ \ \ :\:\:f|)>. \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ <\equation> \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ |)> \: \ \ \ \ \>\\> \ \ \ \ \ \ :\:\:g|)> . \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ regular|)> |)>,\.,x|)>> : Representation matrix of >.\ Representation matrix of \\ >: <\equation*> M|)>:=M|)>,\,g|)>. As a consequence of the properties of a representation matrix, we have the following easy property. <\lemma> Let :t|)>\\>>, then |)>,t|)>> drops iff the point ,t|)>\\\\>. Hereafter, we give some example which are focussed on the intersection of the rational curves in the plane > \ >and the intersection of the rational curves in the space >>. \; <\with|color|blue> Function: intersection_curve_plane(curve1,curve2). Function: intersection_curve_space(curve1,curve2). Function: intersection_curve_plane_homogeneous(curve1,varcur1,curve2,varcur2). Function: intersection_curve_space_homogeneous(curve1,varcur1,curve2,varcur2). <\example> |)>>: =3*x,f=-3*x+3*x, f=x+1 >\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ |)>>: =1,g=x, g=x>\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \C> are: <\input> <|input> include "shape/matrixrepresentation/curvesurface.mmx" <\unfolded-io> <|unfolded-io> curve1:=[polynomial(0,0,3),polynomial(0,3,0,-3), polynomial(1,1)] <|unfolded-io> ,-3*x+3*x,x+1|]>> <\unfolded-io> <|unfolded-io> curve2:=[polynomial(1),polynomial(0,1),polynomial(0,0,1)] <|unfolded-io> |]>> <\unfolded-io> <|unfolded-io> intersection_curve_plane(curve1,curve2) <|unfolded-io> ,,,|]>> <\input> <|input> \; <\textput> |,(-0.64720,0.41887) and >.> <\textput> <\example> \ |)>: f=x-*x+*x-33,f=x-25*x+61*x-36, f=x-*x+*x-8, f=1 >.\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ |)>: g=x-*x+*x-3,g=x-6*x+12*x-6, g=x-*x+*x-38, g=1>.\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ > > > are: <\unfolded-io> <|unfolded-io> cur1:=[polynomial(-33,115/2,-49/2,0,1),polynomial(-36,61,-25,0,1), \ \ \ \ \ \ \ polynomial(-8,27/2,-13/2,1),polynomial(1)] <|unfolded-io> -*x+*x-33,x-25*x+61*x-36,x-*x+*x-8,1|]>> <\unfolded-io> <|unfolded-io> cur2:=[polynomial(-3,17/2,-11/2,1),polynomial(-6,12,-6,1),polynomial \ \ \ \ \ \ \ (-38,125/2,-51/2,0,1),polynomial(1)] <|unfolded-io> -*x+*x-3,x-6*x+12*x-6,x-*x+*x-38,1|]>> \; <\unfolded-io> <|unfolded-io> intersection_curve_space(cur1,cur2) <|unfolded-io> ,,,|]>> <\input> <|input> \; \; <\textput> <\big-figure|> Four intersection points : (1,1,0),(0,2,1),(0,3,1) and (-308,-341,-363). The point (-308,-341,-363) doesn't appear in this picture. \; |The intersection point: (-308,-341,-363)> <\example> |)>: f=x-3*x*y+2*x*y+y,f=x*y+2*x*y+2*y, f=x*y+3*y, f=y. > \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ |)>: g=x-*x*y+y,g=x*y+y, g=x*y+2*y, g=y>. \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ >>> are: <\input> <|input> include "shape/matrixrepresentation/curvesurface.mmx" <\unfolded-io> <|unfolded-io> cur1:=[QQ['x,'y]\\"x^3+3*x^2*y+2*x*y^2+y^3",QQ['x,'y] \\"x^2*y+2*x*y^2+2*y^3",QQ['x,'y]\\"x*y^2+3*y^3", QQ['x,'y]\\"y^3"] <|unfolded-io> +3*x*y+2*x*y+y,x*y+2*x*y+2*y,x*y+3*y,y|]>> <\unfolded-io> <|unfolded-io> cur2:=[QQ['x,'y]\\"x^4-x*y^3+y^4",QQ['x,'y]\\"x*y^3+y^4",QQ['x,'y]\\"x*y^3+2*y^4",QQ['x,'y]\\"y^4"] <|unfolded-io> -x*y+y,x*y+y,x*y+2*y,y|]>> <\unfolded-io> <|unfolded-io> varcur:=[QQ['x,'y]\\"x",QQ['x,'y]\\"y"] <|unfolded-io> > <\unfolded-io> <|unfolded-io> intersection_curve_space_homogeneous(cur1,varcur,cur2,varcur) <|unfolded-io> ,|]>> <\input> <|input> \; <\textput> |The intersection points in the affine space: (1,2,3) and (1,1,2).> <\textput> <\textput> <\equation*> |)> \ \ \:>>>\>>>:\:y:z:w|)>. \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ |)> \ \:>>>\>>>:\:f:f:f|)>>. \; : > matrix representation of the surface >>. M(s,t): matrix representation of \ \\>>:\ <\equation*> M=M,y,z,w|)> and we have the following easy property: <\lemma> Let :t|)>\\>>, then rank of ,t|)>> drops iff \ ,t|)>:y,t|)>:z,t|)>:w,t|)>|)> \\\\>. <\em> \; <\textput> <\example> Sphere |)>: f=x+y+z, f=2*x*z, f=2*x*y,f=x-y-z>.\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ Twisted cubic |)>: g=s,g=s*t, g=s*t,g=t>. \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ > are: <\input> <|input> include "shape/matrixrepresentation/curvesurface.mmx" <\unfolded-io> <|unfolded-io> R:=QQ['s,'t,'x,'y,'z] <|unfolded-io> > <\unfolded-io> <|unfolded-io> sur:=[R\\"x^2+y^2+z^2",R\\"2*x*z",R\\"2*x*y",R\\"x^2-y^2-z^2"] <|unfolded-io> +y+z,2*x*z,2*x*y,x-y-z|]>> <\unfolded-io> <|unfolded-io> cur:=[R\\"t^3",R\\"s*t^2",R\\"s^2*t",R\\"s^3"] <|unfolded-io> ,s*t,s*t,s|]>> <\unfolded-io> <|unfolded-io> varsur:=[R\\"x",R\\"y",R\\"z"] <|unfolded-io> > <\unfolded-io> <|unfolded-io> varcur:=[R\\"s",R\\"t"] <|unfolded-io> > <\unfolded-io> <|unfolded-io> intersection_curve_surface_homogeneous(sur,varsur,cur,varcur) <|unfolded-io> ,,,-0.77184450634604-1.1151425080399*\,-1.5674963658003+0.19339462037529*\|]>,,-0.77184450634604+1.1151425080399*\,-1.5674963658003-0.19339462037529*\|]>,,-0.77184450634604+1.1151425080399*\,1.5674963658003+0.19339462037529*\|]>,,-0.77184450634604-1.1151425080399*\,1.5674963658003-0.19339462037529*\|]>|]>> <\input> <|input> \; \; <\textput> |Two intersection points in the affine space : (-0.73735, 0.54368, -0.40089) and (0.73735, 0.54368, 0.40089)> <\textput> <\example> Steiner's Roman Surface |)>: f=x+y+z, f=y*z,f=x*z,f=x*y. >\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ |)>: g=s+s*t+t,g=s*t,g=s*t,g=t>.\ Then > are:\ <\input> <|input> include "shape/matrixrepresentation/curvesurface.mmx" <\unfolded-io> <|unfolded-io> steiner:=[R\\"x^2+y^2+z^2", R\\"y*z", R\\"x*z", R\\"x*y"] <|unfolded-io> +y+z,y*z,x*z,x*y|]>> <\unfolded-io> <|unfolded-io> varsteiner:=[R\\"x",R\\"y",R\\"z"] <|unfolded-io> > <\unfolded-io> <|unfolded-io> cur:=[R\\"s^3+s*t^2+t^3",R\\"s^2*t",R\\"s*t^2", R\\"t^3"] <|unfolded-io> +s*t+t,s*t,s*t,t|]>> <\unfolded-io> <|unfolded-io> varcur:=[R\\"s", R\\"t"] <|unfolded-io> > <\unfolded-io> <|unfolded-io> intersection_curve_surface_homogeneous(steiner,varsteiner,cur,varcur) <|unfolded-io> ,,|]>> <\input> <|input> \; <\textput> \ |The intersection point in the affine space: (0,0,1),,,|)>> and (0,0,0).> <\session|mathemagix|default> <\textput> <\textput> Let >> be a rational curve of parameterized by <\eqnarray*> :>>>\>>>:\:y:z|)>>||>>> <\textput> <\session|mathemagix|default> <\definition> A mutiplicity of a point \> is number of parametervalues (including multiplicities) > such that |)>=P>. Denote >. <\textput> <\remark> This definition corresponds to the classical definition of multiplicity. Function: singular_point_plane(curve,varcur,int)\ int:=>. > <\textput> <\example> \ |)>: f=t-2*t+2, f=t+3, f=1 >.\ \ > of multiplicity 2 and > of multiplicity 3.\ <\input> <|input> include "shape/matrixrepresentation/singular_point.mmx" <\input> <|input> R:=QQ['t,'x,'y,'z]; <\unfolded-io> <|unfolded-io> curve1:=[R\\"t^5-2*t^3+2", R\\"t^4+3", R\\"1"] <|unfolded-io> -2*t+2,t+3,1|]>> <\input> <|input> varcur:=[R\\"t",R\\"x",R\\"y",R\\"z"]; <\unfolded-io> <|unfolded-io> singular_point_plane(curve1,varcur,2) <|unfolded-io> ,-1.000000000000,1.0000000000000|]>,,-1.000000000000,1.0000000000000|]>,|]>> <\unfolded-io> <|unfolded-io> singular_point_plane(curve1,varcur,3) <|unfolded-io> |]>> <\unfolded-io> <|unfolded-io> singular_point_plane(curve1,varcur,4) <|unfolded-io> > <\textput> |P(2,7) of multiplicity 2 and Q(2,3) of multiplicity 3> <\textput> <\example> (Chen and all) |)>: f=t-40*t+40*t+1, f=t+480*t+1, f=t+40*t+480*t+40*t+1>. <\input> <|input> include "shape/matrixrepresentation/singular_point.mmx" <\unfolded-io> <|unfolded-io> curve2:=[R\\"t^4-40*t^3+40*t+1", R\\"t^4+480*t^2+1", R\\"t^4+40*t^3+480*t^2+40*t+1"] <|unfolded-io> -40*t+40*t+1,t+480*t+1,t+40*t+480*t+40*t+1|]>> <\unfolded-io> <|unfolded-io> singular_point_plane(curve2,varcur,2) <|unfolded-io> ,,,,|]>> <\unfolded-io> <|unfolded-io> singular_point_plane(curve2,varcur,3) <|unfolded-io> > <\textput> <\example> (Busé and D'Andrea)|)>: \ f=t**, f=t**+2*t+1|)>, f=->. <\input> <|input> include "shape/matrixrepresentation/singular_point.mmx" <\input> <|input> f:=R\\"t";g:=R\\"t+1";h:=R\\"2*t+1";k:=R\\"3*t^2+2*t+1"; <\unfolded-io> <|unfolded-io> curve3:=[f^2*g^6*h^2,f^3*h^2*k,-g^10] <|unfolded-io> +28*t+85*t+146*t+155*t+104*t+43*t+10*t+t,12*t+20*t+15*t+6*t+t,-t-10*t-45*t-120*t-210*t-252*t-210*t-120*t-45*t-10*t-1|]>> <\unfolded-io> <|unfolded-io> singular_point_plane(curve3,varcur,2) <|unfolded-io> ,0.02939631279-0.1320590709*\,1.0737e-6-4.8234e-6*\|]>,,0.02939631279+0.1320590709*\,1.0737e-6+4.8234e-6*\|]>,,0.17108079485+0.25281733354*\,1.614649e-4+2.38607e-4*\|]>,,0.17108079485-0.25281733354*\,1.614649e-4-2.38607e-4*\|]>,,-0.010886938234+0.011694109431*\,0.00527448666-0.00566554369*\|]>,,-0.010886938234-0.011694109431*\,0.00527448666+0.00566554369*\|]>,,10.5610777917-4.0202494925*\,-1.31973e-4+5.0238e-5*\|]>,,10.5610777917+4.0202494925*\,-1.31973e-4-5.0238e-5*\|]>,,-0.038355110852+0.02631237164*\,-0.2776126404-0.15515714299*\|]>,,-0.038355110852-0.02631237164*\,-0.2776126404+0.15515714299*\|]>,,-0.36904786637+0.98604069795*\,-0.6539068854+1.7471413884*\|]>,,-0.36904786637-0.98604069795*\,-0.6539068854-1.7471413884*\|]>,,0.565041788527-2.06631904974*\,-10.9458525390-9.7326069137*\|]>,,0.565041788527+2.06631904974*\,-10.9458525390+9.7326069137*\|]>|]>> <\unfolded-io> <|unfolded-io> singular_point_plane(curve3,varcur,3) <|unfolded-io> > <\unfolded-io> <|unfolded-io> singular_point_plane(curve3,varcur,4) <|unfolded-io> ,0e-13+0e-13*\,-9.7656250e-4|]>,|]>> <\unfolded-io> <|unfolded-io> singular_point_plane(curve3,varcur,6) <|unfolded-io> ,-2.00000000000,0e-10+0e-10*\|]>|]>> <\input> <|input> \; <\textput> <\textput> <\itemize-dot> Introduce new matrix- based representation of rational space curves and parameterized surfaces. Transfer the solving of the curve/curve, curve/surface intersection problem into the eigenvalues computing problems. Remove the Kronecker>>>> blocks of the pencil of matrices in order to extract the regular pencil -t*B>. Illustrate the advantages of matrix representation by addressing several impotant problems: the intersection problems and the computation of singularities of rational curves.\ <\textput> <\session|mathemagix|default> <\session|mathemagix|default> <\textput> <\textput> Let > be univariate polynomial with the rational coefficients. >is given to find all roots of equation =0>. <\input> <|input> include "shape/matrixrepresentation/solvepolynomial.mmx" <\unfolded-io> <|unfolded-io> f:=QQ['x]\\"x^40+x^3-x^2+x+1" <|unfolded-io> +x-x+x+1> <\unfolded-io> <|unfolded-io> solve f <|unfolded-io> ,-1.0049834251521-0.17196726032025*\,-0.96347745900439+0.33870289201146*\,-0.96347745900439-0.33870289201146*\,-0.89530531662493+0.49538310771710*\,-0.89530531662493-0.49538310771710*\,-0.80227812149382+0.63766154901237*\,-0.80227812149382-0.63766154901237*\,-0.68707794843886+0.76164469116062*\,-0.68707794843886-0.76164469116062*\,-0.55313394270679+0.86394495156841*\,-0.55313394270679-0.86394495156841*\,-0.40449558768271+0.94178234079554*\,-0.40449558768271-0.94178234079554*\,-0.24572172581447+0.99309581767269*\,-0.24572172581447-0.99309581767269*\,-0.081785101746196+1.0166628713015*\,-0.081785101746196-1.0166628713015*\,0.082011116415606+1.0122677197607*\,0.082011116415606-1.0122677197607*\,0.24016442812963+0.98103370749108*\,0.24016442812963-0.98103370749108*\,0.38753181627060+0.92608254194339*\,0.38753181627060-0.92608254194339*\,0.52141394046064+0.85276429179570*\,0.52141394046064-0.85276429179570*\,0.75622722430548+0.66055592481898*\,0.75622722430548-0.66055592481898*\,0.85444256429696+0.53718069049834*\,0.85444256429696-0.53718069049834*\,0.93267665086038+0.39665860878893*\,0.93267665086038-0.39665860878893*\,0.64380241924431+0.76494670664052*\,0.64380241924431-0.76494670664052*\,0.98682345781911+0.24324949759165*\,0.98682345781911-0.24324949759165*\,1.0144599644734+0.081964272388007*\,1.0144599644734-0.081964272388007*\,-0.54368901270080|]>> <\unfolded-io> <|unfolded-io> g:=polynomial(0,0,1) <|unfolded-io> > <\unfolded-io> <|unfolded-io> solve g^2 <|unfolded-io> > <\textput> <\itemize-dot> Denote by >the set homogemeous polynomial of degree k and \\> then matrix reperesentation of graded Koszul map (in the standard basis) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ : \\\, g\g*f> \ \ \ \ \ \ \ \ \ <\input> <|input> include "shape/matrixrepresentation/curvesurface.mmx" <\unfolded-io> <|unfolded-io> f:=QQ['s,'t]\\"s^3+2*s^2*t-t^3" <|unfolded-io> +2*s*t-t> <\unfolded-io> <|unfolded-io> degree f <|unfolded-io> <\unfolded-io> <|unfolded-io> var:=[QQ['s,'t]\\"s",QQ['s,'t]\\"t"] <|unfolded-io> > <\unfolded-io> <|unfolded-io> matrix_multiply_curve(f,var,2,3) <|unfolded-io> |||||>>|]>> <\unfolded-io> <|unfolded-io> matrix_multiply_curve(f,var,3,3) <|unfolded-io> ||||||>>|]>> <\textput> \; <\textput> <\itemize-dot> Denote by >the set homogemeous polynomial of degree k and \\> then matrix reperesentation of graded Koszul map (in the standard basis) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ : \\\, \ \ \ g\g*f> \; <\unfolded-io> <|unfolded-io> f:=QQ['s,'t,'u]\\"s^2-2*t^2+u^2" <|unfolded-io> -2*t+u> <\unfolded-io> <|unfolded-io> degree f <|unfolded-io> <\unfolded-io> <|unfolded-io> var:=[QQ['s,'t,'u]\\"s",QQ['s,'t,'u]\\"t",QQ['s,'t,'u]\\"u"] <|unfolded-io> > <\unfolded-io> <|unfolded-io> matrix_multiply_surface(f,var,2,2) <|unfolded-io> ||||||||||||||>>|]>> <\unfolded-io> <|unfolded-io> matrix_multiply_surface(f,var,3,2) <|unfolded-io> ||||||||||||||||||||>>|]>> <\textput> Given two polynomials , g\ \> with =gcd,g|)>>. It exits two polynomials of smallest degree , v\ \> such that *f+v*g=d>. give ,u,v|]>>. <\input> <|input> include "shape/matrixrepresentation/EEA.mmx" <\unfolded-io> <|unfolded-io> f:=QQ['x]\\"x^3+3*x-4" <|unfolded-io> +3*x-4> <\unfolded-io> <|unfolded-io> g:=QQ['x]\\"x^5-3*x^4+4*x-2" <|unfolded-io> -3*x+4*x-2> <\unfolded-io> <|unfolded-io> EEA(f,g) <|unfolded-io> *x-,*x-*x-*x+,*x+|]>> <\unfolded-io> <|unfolded-io> gcd(f,g) <|unfolded-io> <\unfolded-io> <|unfolded-io> L:=EEA(f,g) <|unfolded-io> *x-,*x-*x-*x+,*x+|]>> <\unfolded-io> <|unfolded-io> L[1]*f+L[2]*g <|unfolded-io> *x-> <\textput> <\unfolded-io> <|unfolded-io> L:=[b1,b2,b3,b4] <|unfolded-io> > <\unfolded-io> <|unfolded-io> delete(L,b1) <|unfolded-io> > <\unfolded-io> <|unfolded-io> delete(L,b4) <|unfolded-io> > <\unfolded-io> <|unfolded-io> delete(L,a) <|unfolded-io> > <\unfolded-io> <|unfolded-io> L:=[b1,b1,b2,b2,b3,b4,b4,b4] <|unfolded-io> > <\unfolded-io> <|unfolded-io> delete_dif L <|unfolded-io> > <\input> <|input> \; \; <\textput> <\textput> <\itemize-dot> Using subresultant of > -basis to solve \ some problems of rational space curves. Intersection multiplicity problem between two rational curves. Intersection parameterized surface/surface. Singular points of parameterized surfaces. Develop the implementation of the software Mathemagix to solve the above purposes.\ <\textput> <\textput> 1. N. Song, R. Goldman, >-bases for polynomial systems in one variable>, Comput. Aided Geom. Design 26(2) (2009) 217--230. 2. T. Luu Ba, L. Busé, B. Mourrain, , in: SNC '09: Proceedings of the 2009 conference on Symbolic numeric computation, ACM, New York, NY, USA, 2009, pp. 71--78. 3. L. Busé and M. Chardin, . J. Symbolic Comput. 40(4-5): 1150-1168, 2005. 4. L. Busé and T. Luu Ba, . To appear Computed Aided Geometric Design 2010. 5. F. Chen, W. Wang and Y. Liu, J. Symbolic Comput. 43 , 92-117, 2008. 6. The software Axel (http://axel.inria.fr) and Mathemagix (http://www.mathemagix.org). \; \; <\initial> <\collection>