

last edited 15 years ago by Bill Page 
1  
Editor: Bill Page
Time: 2007/11/13 18:38:43 GMT8 

Note: transferred from axiomdeveloper.org 
changed:  Here is what I got so far by translating Amit Khetans bires.mpl into Axiom (I'm struggling with guessing the right coercions...) Help is very much appreciated!:: )abbrev package BIRES bires ++ Description: ++ This package implements Amit Khetan's bivariate resultant algorithm bires(R:Ring, VarSet: List Symbol): Exports == Implementation where polR == DistributedMultivariatePolynomial(VarSet, R) VarList == OrderedVariableList(VarSet) Exports == with resultant: (List polR) > Matrix polR Implementation == add resultant(polylist) == supp := parts(union(union(set(primitiveMonomials(polylist.1))\$Set(polR), set(primitiveMonomials(polylist.2))\$Set(polR)), set(primitiveMonomials(polylist.3))\$Set(polR))) vars := [index(1), index(2)]\$List(VarList) C := matrix [[coefficient(polylist.i, vars, degree(supp.j, vars)) for i in 1..3] for j in 1..#supp] From BillPage Fri Aug 27 13:41:57 0500 2004 From: Bill Page Date: Fri, 27 Aug 2004 13:41:57 0500 Subject: What kind of help? MessageID: <200408271341570500@page.axiomdeveloper.org> Could you explain a little more about what this code is intended to do? What problems in particular are you having? If you stick this code between !\begin{axiom} ... \end{axiom} will it compile? How does one use it? Where can one go to read about "Amit Khetan's bivariate resultant algorithm"? From MartinRubey Sat Aug 28 09:19:18 0500 2004 From: Martin Rubey Date: Sat, 28 Aug 2004 09:19:18 0500 Subject: What kind of help? MessageID: <16688.44982.274092.116123@gargle.gargle.HOWL> InReplyTo: <200408271341570500@page.axiomdeveloper.org> What I need is a fast way to detect whether three given bivariate polynomials have a common nontrivial root, i.e., a root different from (0,0). The nontriviality condition is important, since the polynomials arising in my application will never have a constant term, hence, (0,0) will always be a solution. My current solution to this problem is to do something like res1:=resultant(p1,p2,x) res2:=resultant(p1,p3,x) result:=gcd(res1,res2) In fact, this gives me a complete solution of the system. Unfortunately, for my application this is too slow. The problem is that res1 and res2 are huge polynomials, since p1, p2 and p3 have total degree about 30 and larger. So, hoping for a faster method, I stumbled over multivariate resultants, which achieve nearly what I need, the only problem being the nontriviality condition. I was advised to look at Amit Khetan's algorithm, and, in the hope of somehow solving this latter problem, I began to translate his algorithm, available online from http://www.math.umass.edu/~khetan/software/bires.mpl However, I have not pursued this further, since simple tests in Maple showed that his implementation is in fact a lot slower than my naive algorithm. In fact, it seems that his algorithm is not especially well suited for my problem at hand. I contacted Amit, and he said he would try to help me next week. Martin
Here is what I got so far by translating Amit Khetans bires.mpl into Axiom (I'm struggling with guessing the right coercions...) Help is very much appreciated!:
)abbrev package BIRES bires ++ Description: ++ This package implements Amit Khetan's bivariate resultant algorithm bires(R:Ring, VarSet: List Symbol): Exports == Implementation where polR == DistributedMultivariatePolynomial(VarSet, R) VarList == OrderedVariableList(VarSet) Exports == with resultant: (List polR) > Matrix polR Implementation == add resultant(polylist) == supp := parts(union(union(set(primitiveMonomials(polylist.1))$Set(polR), set(primitiveMonomials(polylist.2))$Set(polR)), set(primitiveMonomials(polylist.3))$Set(polR))) vars := [index(1), index(2)]$List(VarList) C := matrix [[coefficient(polylist.i, vars, degree(supp.j, vars)) for i in 1..3] for j in 1..#supp]
My current solution to this problem is to do something like
res1:=resultant(p1,p2,x) res2:=resultant(p1,p3,x) result:=gcd(res1,res2)
In fact, this gives me a complete solution of the system. Unfortunately, for my application this is too slow. The problem is that res1 and res2 are huge polynomials, since p1, p2 and p3 have total degree about 30 and larger. So, hoping for a faster method, I stumbled over multivariate resultants, which achieve nearly what I need, the only problem being the nontriviality condition. I was advised to look at Amit Khetan's algorithm, and, in the hope of somehow solving this latter problem, I began to translate his algorithm, available online from
http://www.math.umass.edu/~khetan/software/bires.mpl
However, I have not pursued this further, since simple tests in Maple showed that his implementation is in fact a lot slower than my naive algorithm. In fact, it seems that his algorithm is not especially well suited for my problem at hand. I contacted Amit, and he said he would try to help me next week.
Martin