GCD algorithms

[Jay Sharma]

I want to know that for sparse and dense polynomials which gcd algorithms does sagemath uses ?

[David Roe]

It depends on what the base ring is.  In general in Sage you can use two question marks to look at the source code.  For example:

sage: R.<x> = ZZ[]

sage: f = x^2 - 1

sage: f.gcd??

...

cdef Polynomial_integer_dense_flint _right = <Polynomial_integer_dense_flint> right
if self.is_zero() or _right.is_one():
    return right
elif self.is_one() or _right.is_zero():
    return self

cdef Polynomial_integer_dense_flint x = self._new()
sig_on()
fmpz_poly_gcd(x.__poly, self.__poly,
(<Polynomial_integer_dense_flint>right).__poly)
sig_off()
return x

So in this case Sage is delegating the work to FLINT, so you''ll need to look at their documentation/source code to see what the algorithm used is.

David

[Jay Sharma]

I want know that which algorithms sagemath used for computing the gcd of sparse polynomial calculation.

Please also know provide the source of that where can I find this algorithms

On Sat, 25 Mar, 2023, 02:06 Jay Sharma, <jaysha...@gmail.com> wrote:

I want to know that for sparse and dense polynomials which gcd algorithms does sagemath uses ?

--
You received this message because you are subscribed to the Google Groups "sage-gsoc" group.
To unsubscribe from this group and stop receiving emails from it, send an email to sage-gsoc+...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/sage-gsoc/cb8f9e55-be48-400e-925b-e0f1a75c5846n%40googlegroups.com.

[David Roe]

If you create a sparse polynomial ring and use ?? analogously you'll be able to find the source code for gcd.  I don't know off the top of my head what algorithm is used.

David

[Jay Sharma]

Yeah, I create the ring and use 

Can you give the path, where can I get the source code?

To view this discussion on the web visit https://groups.google.com/d/msgid/sage-gsoc/40bd4ae9-38f9-4c50-9d08-d3bc814722ddn%40googlegroups.com.

[tcscrims]

You can see the path in the output of `??`.

Best,

Travis