login  home  contents  what's new  discussion  bug reports     help  links  subscribe  changes  refresh  edit

Edit detail for Multivariate Resultants revision 1 of 1

1
Editor: Bill Page
Time: 2007/11/13 18:38:43 GMT-8
Note: transferred from axiom-developer.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?
Message-ID: <20040827134157-0500@page.axiom-developer.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?
Message-ID: <16688.44982.274092.116123@gargle.gargle.HOWL>
In-Reply-To: <20040827134157-0500@page.axiom-developer.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]

What kind of help? --Bill Page, Fri, 27 Aug 2004 13:41:57 -0500 reply
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"?

What kind of help? --Martin Rubey, Sat, 28 Aug 2004 09:19:18 -0500 reply
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