> On 10/22/18 9:55 AM, Waldek Hebisch wrote:
> > I looked at noncommutative factorization code and AFAICS
> > 'xdpolyf1.spad' has serious problem. One example is:
> >
> > (58) -> factor((x^2 - 2)*(y - 1)*(x - 1))
> >
> > 2 2 3 2
> > (58) [- 2 + 2 y + 2 x - 2 y x + x - x y - x + x y x]
> > Type:
> > List(XDistributedPolynomial(OrderedVariableList([x,y,z,w,x1,x2,x3,x4,x5]),Integer))
> >
> > that is '(x^2 - 2)*(y - 1)*(x - 1)' is treated as irreducible.
> >
Thank you for this example. As noted in the source code the purpose
of the heuristic for finding variables that can be set to zero is to
provide a shortcut that makes the solution more efficient for larger
systems of equations but this heuristic can sometimes fail to produce
a consistent set of equations. This is solved by considering
successively smaller subsets of variables that might be set to zero.
Your example triggers a case where the existing code fails to try hard
enough. The following patch corrects this problem:
~/ncpoly$ git diff
diff --git a/xdpolyf1.spad b/xdpolyf1.spad
index d91cf4a..dc1d002 100644
--- a/xdpolyf1.spad
+++ b/xdpolyf1.spad
@@ -145,16 +145,24 @@ XDistributedPolynomialFunctions1(ALPHABET:List
Symbol, F:Join(IntegralDomain,Gcd
else
s0: List Equation G := []
- while empty? s0 for fp in v repeat
- --output("try: ", fp::OutputForm)
- s := solve(e1,remove(fp,v))$SystemSolvePackage(F)
- while empty? s0 for s1 in s repeat
- m := map(explicit, s1)
- if #s1>0 and reduce(_and$Boolean, m) then s0:=s1
- --output("s0: ",s0::OutputForm)
-
- if empty? s0 then
- return [p]
+ while empty? s0 repeat
+ while empty? s0 for fp in v repeat
+ --output("try: ", fp::OutputForm)
+ s := solve(e1,remove(fp,v))$SystemSolvePackage(F)
+ while empty? s0 for s1 in s repeat
+ m := map(explicit, s1)
+ if #s1>0 and reduce(_and$Boolean, m) then s0:=s1
+ --output("s0: ",s0::OutputForm)
+
+ if empty? s0 then
+ if empty? lz then
+ return [p]
+ else
+ -- try harder!
+ lz := bisect(lz,e)
+ e1 := eval(e,lz)
+ v := members set(concat map(variables, e1))$Set(Symbol)
+
sz := concat(lz,s0)
-- choose a parameter value to make G retractable to F
with the following result:
(45) -> factor((x^2 - 2)*(y - 1)*(x - 1))
2
(45) [2 - x , 1 - y, - 1 + x]
Type:
List(XDistributedPolynomial(OrderedVariableList([x,y,z,w,x1,x2,x3,x4,x5]),Integer))
Time: 0.00 (IN) + 0.09 (EV) + 0.01 (OT) = 0.10 sec
> > More generally, factorization via equation solving directly
> > gives absolute factorization, that is factorization over algebraic
> > closure of base field. To get factorization over base field
> > one needs to recombine factors.
I am not convinced that this is the case.
> > IIUC 'xdpolyf1.spad' tries
> > various tricks to avoid algebraic extentions, but this is
> > very unlikely to work in general.
> >
The tricks in xdpolyf1 having nothing to do with avoiding algebraic
extensions. radicalSolve is only called if the base ring has
RadicalCategory, otherwise SystemSolvePackage only looks for solutions
in fraction field and xdpolyf1 lifts that solution to the base ring.
Are you claiming that this does not provide the most general
factorization in the base ring? Are you suggesting that if one looked
for factorizations over the algebraic closure and then recombined some
factors it might be possible to general polynomials over the base ring
that are not considered when directly solving the factorization
equations over the fraction field?
On Tue, Oct 23, 2018 at 6:47 PM Ray <raymond.roger...@gmail.com> wrote:
> I tried this on my saved version (part of a test -harness) and it works
> correctly.
> Here is the result
> (52) -> aa:=(x^2 - 2)*(y - 1)*(x - 1)
>
> 2 2 3 2
> (52) - 2 + 2 y + 2 x - 2 y x + x - x y - x + x y x
> Type:
> XDistributedPolynomial(OrderedVariableList([x,y,z]),Fraction(MultivariatePolynomial([a,b,c,d,e],Integer)))
> (53) -> factor(aa)
>
> 2
> (53) [- 2 + x , 1 - y, 1 - x]
> Type:
> List(XDistributedPolynomial(OrderedVariableList([x,y,z]),Fraction(MultivariatePolynomial([a,b,c,d,e],Integer))))
> --
Note that you are not using the same polynomial base ring as Waldek,
i.e. Fraction(MultivariatePolynomial([a,b,c,d,e],Integer))) versus
Integer.
--
You received this message because you are subscribed to the Google Groups
"FriCAS - computer algebra system" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to fricas-devel+unsubscr...@googlegroups.com.
To post to this group, send email to fricas-devel@googlegroups.com.
Visit this group at https://groups.google.com/group/fricas-devel.
For more options, visit https://groups.google.com/d/optout.
