Opened 11 years ago

Closed 7 years ago

Last modified 7 years ago

#10058 closed defect (fixed)

Segfault in backward and inverse FFT for 2**n elements

Reported by: mpatel Owned by: jason, jkantor
Priority: major Milestone: sage-6.2
Component: numerical Keywords: gsl, fft, segfault
Cc: wdj Merged in:
Authors: Mike Hansen, Luis Felipe Tabera Alonso, Marc Mezzarobba Reviewers: Luis Felipe Tabera Alonso, Marc Mezzarobba, Punarbasu Purkayastha
Report Upstream: N/A Work issues:
Branch: u/mmezzarobba/10058-gsl_fft Commit: 9beddc73f3003afe617d0a4dc76b741b25dd7e50
Dependencies: Stopgaps:

Status badges

Description (last modified by mmezzarobba)

Sage crashes when asked to do a backward or inverse FFT for sizes that are powers of two:

sage: a = FFT(5)
sage: a[1] = 2
sage: a.forward_transform()
sage: a.backward_transform()
sage: a = FFT(4)
sage: a[1] = 2
sage: a.forward_transform()
sage: a.backward_transform()


------------------------------------------------------------
Unhandled SIGSEGV: A segmentation fault occurred in Sage.
This probably occurred because a *compiled* component
of Sage has a bug in it (typically accessing invalid memory)
or is not properly wrapped with _sig_on, _sig_off.
You might want to run Sage under gdb with 'sage -gdb' to debug this.
Sage will now terminate (sorry).
------------------------------------------------------------

This is with 4.6.alpha2.

Joal Heagney reported this problem on sage-devel.

Attachments (3)

trac_10058.patch (3.6 KB) - added by mhansen 11 years ago.
trac_10058.2.patch (2.3 KB) - added by lftabera 8 years ago.
rebase to sage-5.8.beta2
trac_10058_doc.patch (14.0 KB) - added by lftabera 8 years ago.
documentation, doctest, cleanin the plot code, rebased against sage 5.10.beta2

Download all attachments as: .zip

Change History (13)

comment:1 Changed 11 years ago by mpatel

This happens with a.inverse_transform(), too. From near the end of sage/gsl/fft.pyx:

    def backward_transform(self):
        cdef gsl_fft_complex_wavetable * wt
        cdef gsl_fft_complex_workspace * mem
        N = Integer(self.n)
        e = N.exact_log(2)
        if N==2**e:
            gsl_fft_complex_backward(self.data, self.stride, self.n, wt, mem)

Should this be

            gsl_fft_complex_radix2_backward(self.data, self.stride, self.n)

(and similarly for inverse_transform)?

        if N!=2**e:
            mem = gsl_fft_complex_workspace_alloc(self.n)
            wt = gsl_fft_complex_wavetable_alloc(self.n)
            gsl_fft_complex_backward(self.data, self.stride, self.n, wt, mem)
            gsl_fft_complex_workspace_free(mem)
            gsl_fft_complex_wavetable_free(wt)

comment:2 Changed 11 years ago by mpatel

  • Description modified (diff)

Changed 11 years ago by mhansen

Changed 8 years ago by lftabera

rebase to sage-5.8.beta2

comment:3 Changed 8 years ago by lftabera

  • Authors set to Mike Hansen, Luis Felipe Tabera Alonso
  • Description modified (diff)
  • Keywords gsl fft segfault added
  • Reviewers set to Luis Felipe Tabera Alonso
  • Status changed from new to needs_review

I have reviewed (and rebased) the code of M. Hansen and it is correct. I have also added another patch that fills coverage of fft.pyx and cleans the plot code. This second patch needs review.

Apply: trac_10058.2.patch, trac_10058_doc.patch

comment:4 Changed 8 years ago by ppurka

Hello! The patches look good. I have the following comments about the doc patch.

  1. Can you fix the documentation of the functions? It should be like this
    def function(n, p=1):
        """
        Determine the ``n``-th number. Note that I didn't use `n`
        since single backticks will format it in latex.
       
        INPUT:
    
        - ``n`` -- Integer. Description of this parameter
    
        - ``p`` -- Integer (default: 1). Description of this parameter.
    
  1. The following line 180 See `self.plot` for details. should use :meth: to refer to plot. Also, `self.plot` is used in some other functions.
    See :meth:`.plot` for details.
    
  1. pi should also be changed to float in this line
    191	        pi    = sage.symbolic.constants.pi   # should append .n() at the end.
    
  1. In the function plot, the INPUT needs a fix. It should be like this. Also, see 1. for the comment about default values and formatting.
    - ``style`` -- Style of the plot, options are ``"rect"`` or ``"polar"``
    

You can refer to the developer guide for more information about the formatting of docstrings.

EDIT: Some formatting fixes.

Last edited 8 years ago by ppurka (previous) (diff)

Changed 8 years ago by lftabera

documentation, doctest, cleanin the plot code, rebased against sage 5.10.beta2

comment:5 Changed 8 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:6 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:7 Changed 7 years ago by mmezzarobba

  • Authors changed from Mike Hansen, Luis Felipe Tabera Alonso to Mike Hansen, Luis Felipe Tabera Alonso, Marc Mezzarobba
  • Branch set to u/mmezzarobba/10058-gsl_fft
  • Commit set to 9beddc73f3003afe617d0a4dc76b741b25dd7e50
  • Description modified (diff)
  • Reviewers changed from Luis Felipe Tabera Alonso to Luis Felipe Tabera Alonso, Marc Mezzarobba

Gitified and rebased on top of 6.1. The second patch looks good to me, except for minor points that I fixed in my two commits. Could seomeone please check:

  • that I rebased the code correctly;
  • whether you agree with my changes?

(If both are ok, please go ahead and set the ticket's status to positive_review.)

comment:8 Changed 7 years ago by ppurka

  • Reviewers changed from Luis Felipe Tabera Alonso, Marc Mezzarobba to Luis Felipe Tabera Alonso, Marc Mezzarobba, Punarbasu Purkayastha
  • Status changed from needs_review to positive_review

Looks good to me. It applies fine to sage-6.1 and sage/gsl passes all doctests.

On a sidenote, I don't even remember having made those comments earlier. In reply to my comments @lftabera updated a new patch but I never got any email because adding attachments do not generate emails!

In short: add a comment after adding or updating a git branch; otherwise we don't get email notifications!

comment:9 Changed 7 years ago by vbraun

  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:10 Changed 7 years ago by vbraun

Followup at #15799

Note: See TracTickets for help on using tickets.