Changeset 9173792 in git for Singular/LIB/zeroset.lib
- Timestamp:
- Feb 19, 2001, 3:17:50 PM (23 years ago)
- Branches:
- (u'spielwiese', 'fe61d9c35bf7c61f2b6cbf1b56e25e2f08d536cc')
- Children:
- 25c431d26faee1a17b854e49114f755c02aaf1ef
- Parents:
- 584d1f1ad4878b9855984324f19d6383aa60632c
- File:
-
- 1 edited
-
Singular/LIB/zeroset.lib (modified) (36 diffs)
Legend:
- Unmodified
- Added
- Removed
-
Singular/LIB/zeroset.lib
r584d1f1 r9173792 1 // Last change 10.12.2000 2 /////////////////////////////////////////////////////////////////////////////// 3 4 version="$Id: zeroset.lib,v 1.6 2001-01-16 13:48:47 Singular Exp $"; 1 // Last change 12.02.2001 (Eric Westenberger) 2 /////////////////////////////////////////////////////////////////////////////// 3 version="$Id: zeroset.lib,v 1.7 2001-02-19 14:17:50 lossen Exp $"; 5 4 category="Symbolic-numerical solving"; 6 5 info=" … … 11 10 12 11 OVERVIEW: 13 Algorithms for finding the zero-set of a zero-dim. ideal in Q(a)[x_1,.. x_n],12 Algorithms for finding the zero-set of a zero-dim. ideal in Q(a)[x_1,..,x_n], 14 13 Roots and Factorization of univariate polynomials over Q(a)[t] 15 14 where a is an algebric number. Written in the frame of the 16 15 diploma thesis (advisor: Prof. Gert-Martin Greuel) 'Computations of moduli 17 spaces of semiquasihomogenous singularities and an implementation in Singular' 16 spaces of semiquasihomogenous singularities and an implementation in Singular'. 18 17 This library is meant as a preliminary extension of the functionality 19 18 of Singular for univariate factorization of polynomials over simple algebraic … … 26 25 EGCD(f, g) gcd over an algebraic extension field of Q 27 26 Factor(f) factorization of f over an algebraic extension field 28 InvertNumber(c) inverts an element of an algenraic extension field29 LinearZeroSet(I) find the linear (partial) solution of I30 27 Quotient(f, g) quotient q of f w.r.t. g (in f = q*g + remainder) 31 28 Remainder(f,g) remainder of the division of f by g … … 37 34 EGCDMain(f, g) gcd over an algebraic extension field of Q 38 35 FactorMain(f) factorization of f over an algebraic extension field 39 InvertNumberMain(c) inverts an element of an alge nraic extension field36 InvertNumberMain(c) inverts an element of an algebraic extension field 40 37 QuotientMain(f, g) quotient of f w.r.t. g 41 38 RemainderMain(f,g) remainder of the division of f by g … … 44 41 ContainedQ(data, f) f in data ? 45 42 SameQ(a, b) a == b (list a,b) 46 TransferRing() create a new basering (to use ...Main())47 NewBaseRing() create a new basering (return from ...Main())48 SimplifyData(data) reduces entries of data w.r.t. mpoly49 SimplifyPoly(f) reduces coefficients of f w.r.t. mpoly50 SimplifySolution(sol) reduces the entries of sol w.r.t. the ideal mpoly51 43 "; 52 44 … … 68 60 // Improvement : 69 61 // a main problem is the growth of the coefficients. Try Roots(x7 - 1) 70 // ret rurn ideal mpoly !62 // return ideal mpoly ! 71 63 // mpoly is not monic, comes from primitive_extra 72 64 … … 86 78 87 79 proc Roots(poly f) 88 "USAGE: Roots(f); poly f89 PUR OPSE: compute all roots of f in a finite extension of the groundfield80 "USAGE: Roots(f); where f is a polynomial 81 PURPOSE: compute all roots of f in a finite extension of the ground field 90 82 without multiplicities. 91 83 RETURN: ring, a polynomial ring over an extension field of the ground field, 92 containing a list 'roots', poly 'newA', poly 'f': 93 - 'roots' is the list of roots of the polynomial f (no multiplicities) 94 - if the groundfield is Q(a') and the extension field is Q(a), then 95 'newA' is the representation of a' in Q(a). If the basering 96 contains a parameter 'a' and the minpoly remains unchanged then 97 'newA' = 'a'. If the basering does not contain a parameter then 98 'newA' = 'a' (default). 99 - 'f' is the polynomial f in Q(a) (a' being substituted by newA) 84 containing a list 'roots' and polynomials 'newA' and 'f': 85 @format 86 - 'roots' is the list of roots of the polynomial f (no multiplicities) 87 - if the groundfield is Q(a') and the extension field is Q(a), then 88 'newA' is the representation of a' in Q(a). 89 If the basering contains a parameter 'a' and the minpoly remains unchanged 90 then 'newA' = 'a'. 91 If the basering does not contain a parameter then 'newA' = 'a' (default). 92 - 'f' is the polynomial f in Q(a) (a' being substituted by 'newA') 93 @end format 100 94 ASSUME: ground field to be Q or a simple extension of Q given by a minpoly 101 95 EXAMPLE: example Roots; shows an example … … 164 158 165 159 proc RootsMain(poly f) 166 "USAGE: RootsMain(f); poly f167 PURPOSE: compute all roots of f in a finite extension of the ground field160 "USAGE: RootsMain(f); where f is a polynomial 161 PURPOSE: compute all roots of f in a finite extension of the ground field 168 162 without multiplicities. 169 163 RETURN: list, all entries are polynomials 170 _[1] = roots of f, each entry is a polynomial 171 _[2] = 'newA' - if the groundfield is Q(a') and the extension field 172 is Q(a), then 'newA' is the representation of a' in Q(a) 173 _[3] = minpoly of the algebraic extension of the groundfield 174 ASSUME: basering = Q[x,a] ideal mpoly must be defined, it might be 0 ! 164 @format 165 _[1] = roots of f, each entry is a polynomial 166 _[2] = 'newA' - if the groundfield is Q(a') and the extension field 167 is Q(a), then 'newA' is the representation of a' in Q(a) 168 _[3] = minpoly of the algebraic extension of the groundfield 169 @end format 170 ASSUME: basering = Q[x,a] ideal mpoly must be defined, it might be 0! 175 171 NOTE: might change the ideal mpoly !! 176 172 EXAMPLE: example Roots; shows an example … … 304 300 305 301 proc ZeroSet(ideal I, list #) 306 "USAGE: ZeroSet Main(ideal I [, int opt]); ideal I, int opt307 PUR OPSE: compute the zero-set of the zero-dim. ideal I, in a finite extension302 "USAGE: ZeroSet(I [,opt] ); I=ideal, opt=integer 303 PURPOSE: compute the zero-set of the zero-dim. ideal I, in a finite extension 308 304 of the groundfield. 309 305 RETURN: ring, a polynomial ring over an extension field of the ground field, 310 containing a list 'zeroset', a polynomial 'newA', and an ideal 'id'. 311 - 'zeroset' is list of the zeros of the ideal 'I', each zero is 312 an ideal. 313 - if the groundfield is Q(a') and the extension field is Q(a), then 314 'newA' is the representation of a' in Q(a). If the basering 315 contains a parameter 'a' and the minpoly remains unchanged then 316 'newA' = 'a'. If the basering does not contain a parameter then 317 'newA' = 'a' (default). 318 - 'id' is the ideal 'I' in Q(a)[x_1,...] (a' substituted by 'newA') 306 containing a list 'zeroset', a polynomial 'newA', and an 307 ideal 'id': 308 @format 309 - 'zeroset' is the list of the zeros of the ideal I, each zero is an ideal. 310 - if the groundfield is Q(a') and the extension field is Q(a), then 311 'newA' is the representation of a' in Q(a). 312 If the basering contains a parameter 'a' and the minpoly remains unchanged 313 then 'newA' = 'a'. 314 If the basering does not contain a parameter then 'newA' = 'a' (default). 315 - 'id' is the ideal I in Q(a)[x_1,...] (a' substituted by 'newA') 316 @end format 319 317 ASSUME: dim(I) = 0, and ground field to be Q or a simple extension of Q given 320 318 by a minpoly. … … 406 404 407 405 proc InvertNumberMain(poly f) 408 "USAGE: InvertNumberMain(f); poly f406 "USAGE: InvertNumberMain(f); where f is a polynomial 409 407 PURPOSE: compute 1/f if f is a number in Q(a) i.e., f is represented by a 410 408 polynomial in Q[a]. 411 409 RETURN: poly 1/f 412 ASSUME: basering = Q[x_1,...,x_n,a], ideal 'mpoly'must be defined and != 0 !410 ASSUME: basering = Q[x_1,...,x_n,a], ideal mpoly must be defined and != 0 ! 413 411 " 414 412 { … … 449 447 proc LeadTerm(poly f, int i) 450 448 "USAGE: LeadTerm(f); poly f, int i 451 PUR OPSE: compute the leading coef and term of f w.r.t var(i), where the last449 PURPOSE: compute the leading coef and term of f w.r.t var(i), where the last 452 450 ring variable is treated as a parameter. 453 451 RETURN: list of polynomials … … 469 467 470 468 proc Quotient(poly f, poly g) 471 "USAGE: Quotient(f, g); poly f, g;472 PUR OPSE: compute the quotient q and remainder r s.t. f = g*q + r, deg(r) < g469 "USAGE: Quotient(f, g); where f,g are polynomials; 470 PURPOSE: compute the quotient q and remainder r s.t. f = g*q + r, deg(r) < deg(g) 473 471 RETURN: list of polynomials 474 _[1] = quotient q 475 _[2] = remainder r 472 @format 473 _[1] = quotient q 474 _[2] = remainder r 475 @end format 476 476 ASSUME: basering = Q[x] or Q(a)[x] 477 477 EXAMPLE: example Quotient; shows an example … … 503 503 504 504 proc QuotientMain(poly f, poly g) 505 "USAGE: QuotientMain(f, g); poly f, g506 PUR OPSE: compute the quotient q and remainder r s.t. f = g*q + r, deg(r) < g505 "USAGE: QuotientMain(f, g); where f,g are polynomials 506 PURPOSE: compute the quotient q and remainder r s.t. f = g*q + r, deg(r) < deg(g) 507 507 RETURN: list of polynomials 508 _[1] = quotient q 509 _[2] = remainder r 510 ASSUME: basering = Q[x,a] and ideal 'mpoly' is defined (it might be 0), 511 this represents the ring Q(a)[x] together with 'minpoly'. 508 @format 509 _[1] = quotient q 510 _[2] = remainder r 511 @end format 512 ASSUME: basering = Q[x,a] and ideal mpoly is defined (it might be 0), 513 this represents the ring Q(a)[x] together with its minimal polynomial. 512 514 EXAMPLE: example Quotient; shows an example 513 515 " … … 527 529 528 530 proc Remainder(poly f, poly g) 529 "USAGE: Remainder(f, g); poly f, g530 PUR OPSE: compute the remainder of the division of f by g, i.e. a polynomial r531 s.t. f = g*q + r, deg(r) < g.531 "USAGE: Remainder(f, g); where f,g are polynomials 532 PURPOSE: compute the remainder of the division of f by g, i.e. a polynomial r 533 s.t. f = g*q + r, deg(r) < deg(g). 532 534 RETURN: poly 533 535 ASSUME: basering = Q[x] or Q(a)[x] … … 557 559 558 560 proc RemainderMain(poly f, poly g) 559 "USAGE: RemainderMain(f, g); poly f, g560 PUR OPSE: compute the remainder r s.t. f = g*q + r, deg(r) < g561 "USAGE: RemainderMain(f, g); where f,g are polynomials 562 PURPOSE: compute the remainder r s.t. f = g*q + r, deg(r) < deg(g) 561 563 RETURN: poly 562 ASSUME: basering = Q[x,a] and ideal 'mpoly'is defined (it might be 0),563 this represents the ring Q(a)[x] together with 'minpoly'.564 ASSUME: basering = Q[x,a] and ideal mpoly is defined (it might be 0), 565 this represents the ring Q(a)[x] together with its minimal polynomial. 564 566 " 565 567 { … … 579 581 580 582 proc EGCD(poly f, poly g) 581 "USAGE: EGCDMain(f, g); poly f, g 582 PUROPSE: compute the polynomial gcd of f and g over Q(a)[x] 583 RETURN: poly h s.t. h is a greatest common divisor of f and g (not nec. monic) 583 "USAGE: EGCD(f, g); where f,g are polynomials 584 PURPOSE: compute the polynomial gcd of f and g over Q(a)[x] 585 RETURN: polynomial h s.t. h is a greatest common divisor of f and g (not nec. 586 monic) 584 587 ASSUME: basering = Q(a)[t] 585 588 EXAMPLE: example EGCD; shows an example … … 609 612 610 613 proc EGCDMain(poly f, poly g) 611 "USAGE: EGCDMain(f, g); poly f, g612 PUR OPSE: compute the polynomial gcd of f and g over Q(a)[x]614 "USAGE: EGCDMain(f, g); where f,g are polynomials 615 PURPOSE: compute the polynomial gcd of f and g over Q(a)[x] 613 616 RETURN: poly 614 ASSUME: basering = Q[x,a] and ideal 'mpoly'is defined (it might be 0),615 this represents the ring Q(a)[x] together with 'minpoly'.617 ASSUME: basering = Q[x,a] and ideal mpoly is defined (it might be 0), 618 this represents the ring Q(a)[x] together with its minimal polynomial. 616 619 EXAMPLE: example EGCD; shows an example 617 620 " … … 636 639 proc MEGCD(poly f, poly g, int varIndex) 637 640 "USAGE: MEGCD(f, g, i); poly f, g; int i 638 PUR OPSE: compute the polynomial gcd of f and g in the i'th variable641 PURPOSE: compute the polynomial gcd of f and g in the i'th variable 639 642 RETURN: poly 640 643 ASSUME: f, g are polynomials in var(i), last variable is the algebraic number … … 670 673 671 674 proc SQFRNorm(poly f) 672 "USAGE: SQFRNorm(f); poly f 673 PUROPSE: compute the norm of the squarefree polynomial f in Q(a)[x]. 674 RETURN: list 675 _[1] = squarefree norm of g (poly) 676 _[2] = g (= f(x - s*a)) (poly) 677 _[3] = s (int) 675 "USAGE: SQFRNorm(f); where f is a polynomial 676 PURPOSE: compute the norm of the squarefree polynomial f in Q(a)[x]. 677 RETURN: list with 3 entries 678 @format 679 _[1] = squarefree norm of g (poly) 680 _[2] = g (= f(x - s*a)) (poly) 681 _[3] = s (int) 682 @end format 678 683 ASSUME: f must be squarefree, basering = Q(a)[x] and minpoly != 0. 679 684 NOTE: the norm is an element of Q[x] … … 702 707 703 708 proc SQFRNormMain(poly f) 704 "USAGE: SQFRNorm(f); poly f 705 PUROPSE: compute the norm of the squarefree polynomial f in Q(a)[x]. 706 RETURN: list 707 _[1] = squarefree norm of g (poly) 708 _[2] = g (= f(x - s*a)) (poly) 709 _[3] = s (int) 710 ASSUME: f must be squarefree, basering = Q[x,a] and ideal 'mpoly' is equal to 709 "USAGE: SQFRNorm(f); where f is a polynomial 710 PURPOSE: compute the norm of the squarefree polynomial f in Q(a)[x]. 711 RETURN: list with 3 entries 712 @format 713 _[1] = squarefree norm of g (poly) 714 _[2] = g (= f(x - s*a)) (poly) 715 _[3] = s (int) 716 @end format 717 ASSUME: f must be squarefree, basering = Q[x,a] and ideal mpoly is equal to 711 718 'minpoly',this represents the ring Q(a)[x] together with 'minpoly'. 712 719 NOTE: the norm is an element of Q[x] … … 752 759 753 760 proc Factor(poly f) 754 "USAGE: Factor(f); poly f 755 PUROPSE: compute the factorization of the squarefree poly f over Q(a)[t], minpoly = p(a). 756 RETURN: list 757 _[1] = factors (monic), first entry is the leading coefficient 758 _[2] = multiplicities (not yet) 759 ASSUME: basering must be the univariate polynomial ring over a field which 761 "USAGE: Factor(f); where f is a polynomial 762 PURPOSE: compute the factorization of the squarefree poly f over Q(a)[t] 763 RETURN: list with two entries 764 @format 765 _[1] = factors (monic), first entry is the leading coefficient 766 _[2] = multiplicities (not yet implemented) 767 @end format 768 ASSUME: basering must be the univariate polynomial ring over a field, which 760 769 is Q or a simple extension of Q given by a minpoly. 761 NOTE: if basering = Q[t] then this is the built-in 'factorize'.770 NOTE: if basering = Q[t] then this is the built-in @code{factorize} 762 771 EXAMPLE: example Factor; shows an example 763 772 " … … 788 797 789 798 proc FactorMain(poly f) 790 "USAGE: FactorMain(f); poly f791 PUR OPSE: compute the factorization of the squarefree poly f over Q(a)[t],799 "USAGE: FactorMain(f); where f is a polynomial 800 PURPOSE: compute the factorization of the squarefree poly f over Q(a)[t], 792 801 minpoly = p(a). 793 RETURN: list 794 _[1] = factors, first is a constant 795 _[2] = multiplicities (not yet) 796 ASSUME: basering = Q[x,a], represents Q(a)[x] and minpoly. 797 ideal mpoly must be defined, it might be 0 ! 802 RETURN: list with 2 entries 803 @format 804 _[1] = factors, first is a constant 805 _[2] = multiplicities (not yet implemented) 806 @end format 807 ASSUME: basering = Q[x,a], representing Q(a)[x]. An ideal mpoly must 808 be defined, representing the minimal polynomial (it might be 0!). 798 809 EXAMPLE: example Factor; shows an example 799 810 " … … 845 856 proc ZeroSetMain(ideal I, int primDecQ) 846 857 "USAGE: ZeroSetMain(ideal I, int opt); ideal I, int opt 847 PUR OPSE: compute the zero-set of the zero-dim. ideal I, in a simple extension858 PURPOSE: compute the zero-set of the zero-dim. ideal I, in a simple extension 848 859 of the groundfield. 849 860 RETURN: list … … 934 945 proc ZeroSetMainWork(ideal id, intvec wt, int sVars) 935 946 "USAGE: ZeroSetMainWork(I, wt, sVars); 936 PUR OPSE: compute the zero-set of the zero-dim. ideal I, in a finite extension947 PURPOSE: compute the zero-set of the zero-dim. ideal I, in a finite extension 937 948 of the groundfield (without multiplicities). 938 949 RETURN: list, all entries are polynomials … … 942 953 _[4] = name of algebraic number (default = 'a') 943 954 ASSUME: basering = Q[x_1,x_2,...,x_n,a] 944 ideal mpoly must be defined, it might be 0 955 ideal mpoly must be defined, it might be 0! 945 956 NOTE: might change 'mpoly' !! 946 957 EXAMPLE: example IdealSolve; shows an example … … 1098 1109 proc NonLinearZeroSetMain(ideal I, intvec wt) 1099 1110 "USAGE: ZeroSetMainWork(I, wt, sVars); 1100 PUR OPSE: solves the (nonlinear) univariate polynomials in I1111 PURPOSE: solves the (nonlinear) univariate polynomials in I 1101 1112 of the groundfield (without multiplicities). 1102 1113 RETURN: list, all entries are polynomials … … 1186 1197 static proc ExtendSolutions(list solutions, list newSolutions) 1187 1198 "USAGE: ExtendSolutions(sols, newSols); list sols, newSols; 1188 PUR OPSE: extend the entries of 'sols' by the entries of 'newSols',1199 PURPOSE: extend the entries of 'sols' by the entries of 'newSols', 1189 1200 each entry of 'newSols' is a number. 1190 1201 RETURN: list … … 1245 1256 static proc SubsMapIdeal(list sol, list index, int opt) 1246 1257 "USAGE: SubsMapIdeal(sol,index,opt); list sol, index; int opt; 1247 PUR OPSE: built an ideal I as follows.1258 PURPOSE: built an ideal I as follows. 1248 1259 if i is contained in 'index' then set I[i] = sol[i] 1249 1260 if i is not contained in 'index' then … … 1275 1286 proc SimplifyZeroset(data) 1276 1287 "USAGE: SimplifyZeroset(data); list data 1277 PUR OPSE: reduce the entries of the elements of 'data' w.r.t. the ideal 'mpoly'1288 PURPOSE: reduce the entries of the elements of 'data' w.r.t. the ideal 'mpoly' 1278 1289 'data' is a list of ideals/lists. 1279 1290 RETURN: list … … 1296 1307 proc Variables(poly f, int n) 1297 1308 "USAGE: Variables(f,n); poly f; int n; 1298 PUR OPSE: list of variables among var(1),...,var(n) which occur in f.1309 PURPOSE: list of variables among var(1),...,var(n) which occur in f. 1299 1310 RETURN: list 1300 1311 ASSUME: n <= nvars(basering) … … 1314 1325 1315 1326 proc ContainedQ(data, f, list #) 1316 "USAGE: ContainedQ(data, f [, opt]); list data; f is of any type, int opt1317 PUR OPSE: test if 'f' is an element of 'data'.1327 "USAGE: ContainedQ(data, f [, opt]); data=list; f=any type, opt=integer 1328 PURPOSE: test if f is an element of data. 1318 1329 RETURN: int 1319 0 if 'f' not contained in 'data'1320 1 if 'f' contained in 'data'1321 OPTIONS: opt = 0 : use '==' for comparing f with elements from data 1322 opt = 1 : use 'SameQ'for comparing f with elements from data1330 0 if f not contained in data 1331 1 if f contained in data 1332 OPTIONS: opt = 0 : use '==' for comparing f with elements from data@* 1333 opt = 1 : use @code{SameQ} for comparing f with elements from data 1323 1334 " 1324 1335 { … … 1345 1356 1346 1357 proc SameQ(a, b) 1347 "USAGE: SameQ(a, b); list/intvec a, b;1348 PUR OPSE: test a == b elementwise, i.e., a[i] = b[i].1358 "USAGE: SameQ(a, b); a,b=list/intvec 1359 PURPOSE: test a == b elementwise, i.e., a[i] = b[i]. 1349 1360 RETURN: int 1350 1361 0 if a != b … … 1374 1385 static proc SimplifyPoly(poly f) 1375 1386 "USAGE: SimplifyPoly(f); poly f 1376 PUR OPSE: reduces the coefficients of f w.r.t. the ideal 'moly' if they contain1387 PURPOSE: reduces the coefficients of f w.r.t. the ideal 'moly' if they contain 1377 1388 the algebraic number 'a'. 1378 1389 RETURN: poly … … 1399 1410 static proc SimplifyData(data) 1400 1411 "USAGE: SimplifyData(data); ideal/list data; 1401 PUR OPSE: reduces the entries of 'data' w.r.t. the ideal 'mpoly' if they contain1412 PURPOSE: reduces the entries of 'data' w.r.t. the ideal 'mpoly' if they contain 1402 1413 the algebraic number 'a' 1403 1414 RETURN: ideal/list … … 1423 1434 static proc TransferRing(R) 1424 1435 "USAGE: TransferRing(R); 1425 PUR OPSE: creates a new ring containing the same variables as R, but without1436 PURPOSE: creates a new ring containing the same variables as R, but without 1426 1437 parameters. If R contains a parameter then this parameter is added 1427 1438 as the last variable and 'minpoly' is represented by the ideal 'mpoly' … … 1457 1468 static proc NewBaseRing() 1458 1469 "USAGE: NewBaseRing(); 1459 PUR OPSE: creates a new ring, the last variable is added as a parameter.1470 PURPOSE: creates a new ring, the last variable is added as a parameter. 1460 1471 minpoly is set to mpoly[1]. 1461 1472 RETURN: ring
Note: See TracChangeset
for help on using the changeset viewer.
