Question Regarding the Discrete Weighted Transform

[Sane]

Hi! I found this site on Google, and thought I could get your help.

I am in desperate need of understanding something that is very briefly suggested in a research paper.

Given this formula...

http://img505.imageshack.us/img505/702/formka2.png

I know what everything is, except g.

They describe g as "a primitive Nth root of unity in the appropriate domain".

I have no clue what that's supposed to mean. What do I do to find g? I can't see anything else said about g in the rest of the research paper. Help please?

Here it is: http://faginfamily.net/barry/Papers/Discrete%20Weighted%20Transforms.pdf

It's section (2.5).

[OfficeShredder]

I don't know, but it sounds a lot like nth roots of unity for complex numbers. In fact, wikipedia sheds a bit of light perhaps:

http://en.wikipedia.org/wiki/Roots_of_unity

The nth roots of unity form under multiplication a cyclic group of order n, and in fact these groups comprise all of the finite multiplicative subgroups of the complex numbers, except the trivial group {0}. A generator for this cyclic group is a primitive nth root of unity. The primitive nth roots of unity are e2πik / n where k and n are coprime. The number of different primitive nth roots of unity is given by Euler's totient function, φ(n).

So presumably, working in a different domain, you could have different primitive nth roots of unit

[Sane]

Oh, wow. I had no clue "Roots of Unity" was an actual concept. I thought the author was just throwing our random terms.

This is always one area where I dislike Wikipedia... they act more as a resource for reference, rather than a medium for education. I'm not sure if I can clearly grasp how to calculate g, by reading this article alone...

Would someone be as kind as to help me understand how to find "a primitive Nth root of unity in the appropraite domain" for section (2.5)? Meanwhile, I'll go looking for some other sites to see if someone's explained it in their own words.

[OfficeShredder]

Do you know what the appropriate domain is supposed to be? Reading it, I can't really see... I don't have any experience in the topic being presented, but I can roughly understand what's going on in the paper. But I don't see what g is supposed to be.

Nth roots of unity in the complex numbers are easy... they're just numbers of the form

cos(2*pi*k/n) + sin(2*pi*k/n)i for 0<=k<=n

basically, they're the n points spread evenly on the unit circle (and obviously including 1), so you would just look for the roots that can cycle around to all of the other roots (specifically, if multiplying it enough times brings it to e^(2*pi*i/n).

Actually, it describes specifically what the full set of primitive roots is in the paragraph I quoted from wikipedia

[Sane]

I don't know what the appropriate domain is, but I can speculate it is mentioned somewhere in section 6. That section is what references the variant of Algorithm W that I am currently implementing (end of section 3), and specifies what varies in Algorithm W. I'm not sure where the "appropriate domain" is ever mentioned though ...

[OfficeShredder]

Since it doesn't look like your question's getting answered here (hallsofivy might know, but seems mysteriously gone :rolleyes: ) I'll direct you over to physicsforums.com

The much larger population of posters, including a lot of people who know a lot of math, means you have a good chance of getting it answered