Re: [eigen] uniform spaced cpx sinusoid via rootfinding, was Re: FFT module thoughts |

[ Thread Index | Date Index | More lists.tuxfamily.org/eigen Archives ]

*To*: eigen@xxxxxxxxxxxxxxxxxxx*Subject*: Re: [eigen] uniform spaced cpx sinusoid via rootfinding, was Re: FFT module thoughts*From*: Pavel Holoborodko <pavel@xxxxxxxxxxxxxxx>*Date*: Fri, 6 Apr 2012 10:39:35 +0900

Mark, thank you for explaining your ideas. I think it might be a great way to avoid exp() computing (prone to cancellation errors).

Need to study this further, thank you for the Matlab script!

On Fri, Apr 6, 2012 at 12:55 AM, Mark Borgerding <mark@xxxxxxxxxxxxxx> wrote:

To create a root-finder, I'd probably start by trying to use http://en.wikipedia.org/wiki/Newton%27s_method. There might be a more suitable algorithm for finding complex roots of unity.

One could use this root-finder to create an entire cycle via the algorithm in the attached octave/matlab script.

The idea is similar to http://en.wikipedia.org/wiki/CORDIC

The only reason I can think of not to do this for the general case is fear of worst-case numerical performance (e.g. n is a large prime). One thought: This might be mitigated by comparing the complex sinusoid with its time-reversed and conjugated self.

On 04/05/2012 11:02 AM, Pavel Holoborodko wrote:

Hi Mark.[...]

I would really appreciate if you would provide some links on how to re-write make_twiddles using root finding approach.

**References**:**Re: FFT module thoughts, was Re: [eigen] Eigen 3.0.5 Could NOT find FFTW***From:*Pavel Holoborodko

**Re: FFT module thoughts, was Re: [eigen] Eigen 3.0.5 Could NOT find FFTW***From:*Márton Danóczy

**Re: FFT module thoughts, was Re: [eigen] Eigen 3.0.5 Could NOT find FFTW***From:*Pavel Holoborodko

**Re: FFT module thoughts, was Re: [eigen] Eigen 3.0.5 Could NOT find FFTW***From:*Márton Danóczy

**Re: FFT module thoughts, was Re: [eigen] Eigen 3.0.5 Could NOT find FFTW***From:*Björn Piltz

**Re: FFT module thoughts, was Re: [eigen] Eigen 3.0.5 Could NOT find FFTW***From:*Pavel Holoborodko

**Re: FFT module thoughts, was Re: [eigen] Eigen 3.0.5 Could NOT find FFTW***From:*Mark Borgerding

**Re: FFT module thoughts, was Re: [eigen] Eigen 3.0.5 Could NOT find FFTW***From:*Pavel Holoborodko

**[eigen] uniform spaced cpx sinusoid via rootfinding, was Re: FFT module thoughts***From:*Mark Borgerding

**Messages sorted by:**[ date | thread ]- Prev by Date:
**Re: FFT module thoughts, was Re: [eigen] Eigen 3.0.5 Could NOT find FFTW** - Next by Date:
**[eigen] Proposal: Include Constants to NumTraits** - Previous by thread:
**[eigen] uniform spaced cpx sinusoid via rootfinding, was Re: FFT module thoughts** - Next by thread:
**Re: FFT module thoughts, was Re: [eigen] Eigen 3.0.5 Could NOT find FFTW**

Mail converted by MHonArc 2.6.19+ | http://listengine.tuxfamily.org/ |