Opened 8 years ago

Closed 7 years ago

#10910 closed enhancement (duplicate)

Avoid nfinit while factoring polynomials

Reported by: lftabera Owned by: tbd
Priority: major Milestone: sage-duplicate/invalid/wontfix
Component: number fields Keywords: factorization, pari, nfinit, number field, sd32
Cc: Merged in:
Authors: Reviewers: Luis Felipe Tabera Alonso
Report Upstream: Fixed upstream, in a later stable release. Work issues:
Branch: Commit:
Dependencies: #11130 Stopgaps:

Description (last modified by jdemeyer)

In previous versions of pari the options to factor a univariate polynomial over a number field were Trager's or Van Hoeij modular algorithm. The second method is the preferred one, but it used to need a nf structure.

Hence Sage computed nfinit on the number field before factoring the polynomial via Pari.

With current pari version the whole nf structure is not needed. So, the factor routines should not call nfinit that can be a very expensive operation for large fields.

The patch modifies the factor method. If the nf structure is already computed we use it, as it will be faster. If the nf structure is not already computed then do not compute it to factor the polynomial.

See also #11890 for a slightly different solution to the same issue.

Attachments (1)

factor_nfinit_free.patch (5.9 KB) - added by lftabera 8 years ago.
the good one

Download all attachments as: .zip

Change History (15)

comment:1 Changed 8 years ago by lftabera

  • Authors set to Luis Felipe Tabera Alonso
  • Status changed from new to needs_review

comment:2 Changed 8 years ago by lftabera

The doctest failure is known bug that is corrected in #2329.

Depends: #2329

comment:3 Changed 8 years ago by mariah

  • Description modified (diff)

Minor edit of grammer.

comment:4 Changed 8 years ago by mariah

  • Status changed from needs_review to needs_work

The patch applied to sage-4.7.rc2 causes the following test to fail:

% ./sage -t  -long -force_lib "devel/sage/sage/rings/polynomial/polynomial_element.pyx"
sage -t -long -force_lib "devel/sage/sage/rings/polynomial/polynomial_element.pyx"
**********************************************************************
File "/home/mariah/sage/sage-4.7.rc2-x86_64-Linux-nehalem-fc-review-10910/devel/sage/sage/rings/polynomial/polynomial_element.pyx", line 2704:
    sage: hasattr(N, '_NumberField_generic__pari_nf')
Expected:
    False
Got:
    True
**********************************************************************
1 items had failures:
   1 of 143 in __main__.example_51
***Test Failed*** 1 failures.
For whitespace errors, see the file /home/mariah/.sage//tmp/.doctest_polynomial_element.py
         [23.1 s]
 
----------------------------------------------------------------------
The following tests failed:


        sage -t -long -force_lib "devel/sage/sage/rings/polynomial/polynomial_element.pyx"
Total time for all tests: 23.1 seconds

comment:5 Changed 8 years ago by lftabera

Just for the record, my patch introduces the following problem, so I need to add a doctest to it since it is an unapparent side effect.

sage: N = NumberField(x^3-2*x+3,'a')
sage: f = N[x](x^2-41943301)
sage: M = N.extension(f,'b')
sage: M.hom([M.gen()])
...
ValueError: no way to map base field to codomain.

comment:6 Changed 8 years ago by lftabera

  • Report Upstream changed from N/A to Reported upstream. Little or no feedback.
  • Work issues set to pari bug #1207

I have tracked the latest problem and it is in fact a bug in pari. See upstream report #1207.

I have corrected some errors in the code and added another doctest.

I am unable to reproduce the doctest failing that Maria points out on sage-4.7

Note: doctest with this patch will fail until the pari bug is solved.

comment:7 Changed 8 years ago by lftabera

  • Report Upstream changed from Reported upstream. Little or no feedback. to Reported upstream. Developers acknowledge bug.

comment:8 Changed 8 years ago by lftabera

  • Dependencies set to #11130
  • Report Upstream changed from Reported upstream. Developers acknowledge bug. to Fixed upstream, in a later stable release.

The problem with pari is solved in the last stable release.

This ticket now depends on #11130 until pari is not updated the patch is not safe.

Changed 8 years ago by lftabera

the good one

comment:9 Changed 8 years ago by lftabera

  • Status changed from needs_work to needs_review

Rebase against 4.7.1

comment:10 Changed 8 years ago by was

  • Keywords sd32 added

comment:11 Changed 7 years ago by jdemeyer

  • Description modified (diff)

comment:12 Changed 7 years ago by lftabera

This ticked should be closed as a duplicate of #11890

comment:13 Changed 7 years ago by jdemeyer

  • Authors Luis Felipe Tabera Alonso deleted
  • Component changed from factorization to number fields
  • Milestone changed from sage-4.7.2 to sage-duplicate/invalid/wontfix
  • Reviewers set to Luis Felipe Tabera Alonso
  • Status changed from needs_review to positive_review
  • Work issues pari bug #1207 deleted

comment:14 Changed 7 years ago by jdemeyer

  • Resolution set to duplicate
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.