Komputeralgebrai algoritmusok
J\303\241rai Antal
Ezek a programok csak szeml\303\251ltet\303\251sre szolg\303\241lnak.
1. T\303\266rt\303\251net
2. Algebrai alapok
restart;
A 2.1. Algoritmus.
Euclid:=proc(a,b,x) local c,d,r,ua,ub,uc;
if nargs<3 then
c:=abs(a); d:=abs(b);
else
ua:=lcoeff(collect(a,x),x); if ua<>0 then c:=a/ua fi;
ub:=lcoeff(collect(b,x),x); if ub<>0 then d:=b/ub fi;
fi;
while d<>0 do
if nargs<3 then r:=irem(c,d) else r:=rem(c,d,x) fi;
c:=d; d:=r;
od;
if nargs<3 then
abs(c);
else
uc:=lcoeff(collect(c,x),x); if uc<>0 then c/uc else c fi;
fi;
end;
LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2JVEhRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0Yn
A 2.2. Algoritmus.
EEA:=proc(a,b,s,t,x) local c,c1,c2,d,d1,d2,q,r,r1,r2,ua,ub,uc;
if nargs<5 then
c:=abs(a); d:=abs(b);
else
ua:=lcoeff(collect(a,x),x); if ua<>0 then c:=a/ua fi;
ub:=lcoeff(collect(b,x),x); if ub<>0 then d:=b/ub fi;
fi;
c1:=1; d1:=0; c2:=0; d2:=1;
while d<>0 do
if nargs<5 then q:=iquo(c,d) else q:=quo(c,d,x) fi;
r:=expand(c-q*d);
r1:=expand(c1-q*d1);
r2:=expand(c2-q*d2);
c:=d; c1:=d1; c2:=d2;
d:=r; d1:=r1; d2:=r2;
od;
if nargs<5 then
s:=c1/sign(a)/sign(c); t:=c2/sign(b)/sign(c); abs(c);
else
uc:=lcoeff(collect(c,x),x);
if uc<>0 then
if ua<>0 then s:=c1/uc/ua else s:=c1/uc fi;
if ub<>0 then t:=c2/uc/ub else s:=c2/uc fi;
c/uc;
else
if ua<>0 then s:=c1/ua else s:=c1 fi;
if ub<>0 then t:=c2/ub else s:=c2 fi;
c;
fi;
fi;
end;
LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2JVEhRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0Yn
E 2.18. P\303\251lda.
p:=collect(p,[x,y],`distributed`); lcoeff(p,[x,y],'t'); t;
convert(t,list); map(x->op(2,x),%);
degree(p,{x,y});
degree(p,x);
degree(p,y);
LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2JVEhRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0Yn
E 2.21. P\303\251lda.
u:=proc(p,L,typ) local pp,uu;
pp:=expand(p); pp:=collect(pp,L,`distributed`);
uu:=lcoeff(pp,L);
if uu=0 then return 1 fi;
if typ='integer' then return sign(uu) fi;
uu;
end;
cont:=proc(p,L,typ) local pp,uu,cL;
if nops(L)=1 and typ<>'integer' then return 1 fi;
uu:=u(p,L,typ);
pp:=simplify(p/uu);
pp:=collect(pp,L[1]);
cL:=coeffs(pp,L[1]);
if nops(L)=1 then return igcd(cL) fi;
GCD([cL],L[2..nops(L)],typ);
end;
pp:=proc(p,L,typ) local uu,pp,c;
uu:=u(p,L,typ);
pp:=simplify(p/uu);
c:=cont(pp,L,typ);
if c=0 then 0 else simplify(pp/c) fi;
end;
a;
u(a,[x],'integer');
cont(a,[x],'integer');
pp(a,[x],'integer');
u(a,[x],'rational');
cont(a,[x],'rational');
pp(a,[x],'rational');
b;
u(b,[x],'integer');
cont(b,[x],'integer');
pp(b,[x],'integer');
u(b,[x],'rational');
cont(b,[x],'rational');
pp(b,[x],'rational');
LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2JVEhRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0Yn
A 2.3. Algoritmus.
pseudodiv:=proc(a,b,x,q,r) local l,beta,qq,aa,bb;
aa:=collect(expand(a),x);
bb:=collect(expand(b),x);
l:=degree(aa,x)-degree(bb,x)+1;
q:=0;
if l<=0 then r:=aa; return fi;
beta:=lcoeff(bb,x);
aa:=collect(expand(aa*beta^l),x);
while degree(aa,x)>=degree(bb,x) do
l:=degree(aa,x)-degree(bb,x);
qq:=lcoeff(aa,x)/beta;
q:=q+qq;
aa:=collect(expand(aa-qq*x^l*bb),x);
od;
r:=aa;
end;
PrimitiveEuclidean:=proc(a,b,L,typ) local c,d,r,q,gamma;
c:=pp(a,L,typ); d:=pp(b,L,typ);
while d<>0 do
pseudodiv(c,d,L[1],'q','r');
c:=d; d:=pp(r,L,typ);
od;
if nops(L)=1 then
if typ='integer' then
gamma:=igcd(cont(a,L,typ),cont(b,L,typ));
else gamma:=1 fi;
else
gamma:=PrimitiveEuclidean(cont(a,L,typ),cont(b,L,typ),L[2..nops(L)],typ);
fi; gamma*c;
end;
GCD:=proc(P,L,typ)
if nops(P)=0 then return 0 fi;
if nops(P)=1 then return expand(P[1]/u(P[1],L,typ)) fi;
if nops(P)=2 then PrimitiveEuclidean(op(P),L,typ)
else GCD([PrimitiveEuclidean(P[1],P[2],L,typ),op(P[3..nops(P)])],L,typ) fi;
end;
LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2JVEhRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0Yn
E 2.23. P\303\251lda.
aa:=-30*x^3*y+90*x^2*y^2+15*x^2-60*x*y+45*y^2;
bb:=100*x^2*y-140*x^2-250*x*y^2+350*x*y-150*y^3+210*y^2;
aa:=collect(aa,[x,y]);
bb:=collect(bb,[x,y]);
coeffs(aa,x);
coeffs(bb,x);
debug(GCD):
GCD([%%%],[y],'integer');
GCD([%%%],[y],'integer');
undebug(GCD);
pp(aa,[x,y],'integer');
pp(bb,[x,y],'integer');
PrimitiveEuclidean(aa,bb,[x,y],'integer');
LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2JVEhRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0Yn
E 2.29. P\303\251lda.
with(powseries);
c:='c'; powcreate(c(n)=1,c(0)=2,c(1)=0,c(2)=0); tpsform(c,x,8);
d:=powpoly(1-x,x); tpsform(d,x,8);
e:=inverse(d); tpsform(e,x,8);
a:=multiply(e,c); tpsform(a,x,8);
b:=multiply(a,e); tpsform(b,x,8);
LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2JVEhRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0Yn
3. Norm\303\241l form\303\241k, reprezent\303\241ci\303\263
5. K\303\255nai marad\303\251kol\303\241s
6. Newton-iter\303\241ci\303\263, Hensel-felemel\303\251s
7. Legnagyobb k\303\266z\303\266s oszt\303\263
8. Faktoriz\303\241l\303\241s
10. Gr\303\266bner-b\303\241zisok
11. Racion\303\241lis t\303\266rtf\303\274ggv\303\251nyek integr\303\241l\303\241sa
LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2JVEhRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0Yn