Berkeley CSUA MOTD:Entry 28191
Berkeley CSUA MOTD
 
WIKI | FAQ | Tech FAQ
http://csua.com/feed/
2025/07/08 [General] UID:1000 Activity:popular
7/8     

2003/4/22-24 [Academia/Berkeley/Classes, Computer/Theory] UID:28191 Activity:high
4/22    Data Structure: X,Y,Z coordinates repeated. Same X,Y - different Z
        Ie, multiple surfaces over the same grid. Problem: Want a polynomial
        fit f(X,Y)=Z; save the equation in matrix/vector; then the dump into
        MATLAB. Question: a lot of programs do polynomial fits, but it
        seems to be a pain to save the equation describing f(X,Y). What can
        I use to do a large number of curve fittings and then save the
        polynomical eqn? fab@csua
        \_ If you took CS170 you should know the answer to your own question.
           Hint: it starts with an F, and runs in O(n log n) time.
                \_ Didn't take CS170. Care to provide an answer? The question
                 isn't about curve fitting, it's merely about making
                 your favorite software (Stata, SPSS, MATLAB, etc)
                 produce a friggin' macro/list/whatever. fab
                 \_ The data structure itself can be used to represent the
                    fitted polynomials.  You can transform between a 'set of
                    points' representation and 'set of polynomial coefficients'
                    representation using something called Fast Fourier
                    Transform.  I highly suggest you read up on it, any
                    engineer should know what it is.
                        \_ I'm not an engineer. Sorry to disappoint, but if
                        this is routine, I wouldn't mind paying some undergrad
                        a very modest sum to do this for me. fab@csua
                        \_ Dear fab@csua.  Are you really stupid enough to
                           not realize you just offered someone a very modest
                           sum to do nothing at all?  The whole point of FFT is
                           that your original matrix is a perfectly valid
                           representation of the fitted polynomials.
                           \_ I think it's a reasonable guess that anyone
                              not clever enough to indent motd correctly
                              may not be clever enough to do FFT's.
                    \_ I took 170.  We didn't cover that.  Must be new math.
                \_ Boy, there are a lot of wrong answers here. FFT does
                   NOT fit polinomials to data. It fits discrete complex
                   sinusoids to it. This almost certainly isn't what the
                   person wants. Your belligerence is unwarranted, and
                   surpassed by your ineptitude, mr. fft guy.
                   The op should consider performing the polyfit in MATLAB,
                   instead of worrying about how to dump the result to
                   MATLAB. the polyfit function in matlab does this. Also,
                   I don't understand your question, so what nivra said -ali.
                   \_ http://www.mapleapps.com/categories/mathematics/algebra/html/FFT-Polynomial.html
                      \_ this teaches you how to use the FFT to multiply two
                         polynomials. the trick is based on the fact that
                         convolution of the poly coeffs is the same as
                         multiplication of the DFT coeffs. it has nothing
                         to do with polynomial fitting. did you just google
                         for "fft and polynomial" and post the result on
                         the motd? -ali
        \_ I don't get your question.  It seems you're asking for the
           following:  You have n-mesh like 2-D surfaces, you'd like a
           polynomial fit for each surface, resulting in n-sets of polynomial
           equations Z = f(X,Y), You'd like to save all n equations easily.
           Most polynomial fits should give output in terms of coefficients.
           These coefficients form a vector: eg. Ax^2+Bx+Cy^2+Dy+Exy+F.
           You will end up with n sets of coefficeints.  You can save this
           as a big matrix in Matlab.  What's so difficult about this?  If
           you want to do multiple polynomial(2nd order - 10th order) for
           each mesh surface, you run this whole thing 9 times, and get
           1 matrix for each order, with higher order polynomial fits having
           many more vector elements.    -nivra
2025/07/08 [General] UID:1000 Activity:popular
7/8     

You may also be interested in these entries...
2006/9/6-12 [Academia/Berkeley/Classes] UID:44287 Activity:nil
9/6     Papa's got a brand new bag^H^H^H^H book.  On Algorithms.  For the
        time being, a free download.
        http://www.cse.ucsd.edu/users/dasgupta/mcgrawhill
        \_ I think I just had an Umesh Moment[tm]
           \- Momento Umesh:
              http://home.lbl.gov:8080/~psb/ASSOCIATES/UmeshMoment.jpg
	...
2005/2/23-24 [Academia/Berkeley/CSUA/Motd] UID:36383 Activity:high
2/23    So why do people seem so uncomfortable about answering questions
        that seem to come from coursework?  Is it about making students
        suffer, or because of an assumption that they'll learn more by
        doing it the hard way?  The question below is something I hazily
        remember and it's something I'd like to know, just to stay sharp.
        I think NOT answering it, as tends to happen, might send the wrong
	...
2004/7/20-21 [Academia/Berkeley/Classes] UID:32380 Activity:high
9/11    The one that reversed all the words yesterday, how did he do it?
        It was pretty funny.
        \_ Funny?  Yes, destroying other people's discussions (both political
           and technical) is Hi-larious.
        \_ How did he do it? We will never know. Such magnificent text
           processing is unheard of!! But that's the great thing about CSUA,
	...
2002/9/8 [Academia/Berkeley/Classes] UID:25801 Activity:moderate
9/7     alexf, were you in that seminar-like course about 4 years
        ago that steve rudich from cmu taught, which was like a
        cross between cs170 and math 55, but more entertaining?
        \_ Err, that was Spring '98. I was in high school (in SoCal,
           furthermore). That is to say, "no." -alexf
	...
2001/3/16-17 [Academia/Berkeley/Classes, Academia/GradSchool] UID:20812 Activity:high
3/15    What's the best way to study for CS Subject GRE? Thanks.
        \_ Take CS61ABC, CS162, CS164, CS170, CS...
                \_ Yeah right.  Like those teach you anything practical.
                   \_ What are you talking about? I solve NP-complete
                      problems all the time.
                   \_ The issue is not practicality. The issue is prepping
	...
1998/10/14-15 [Academia/Berkeley/Classes] UID:14774 Activity:insanely high
10/14   Sorry, but EECS is hardcore, and CS isn't. It has much more presteige,
        and the recruiters know it - that we EECSs have been abused by
        Hilfinger (willingly) and deserve a few pennies more per year to make
                \_ Dumbshit, I wasn't even CS and I willingly took Hilfinger's
                   classes.  Oh woe is you, the EECS major, boo hoo.  Grow up.
        up for it. Go to hell EECS, and go to hell Berkeley CS proffs.
	...
2012/1/24-3/3 [Computer/SW/Languages/C_Cplusplus, Computer/SW/Languages/Misc] UID:54296 Activity:nil
1/24    http://james-iry.blogspot.com/2009/05/brief-incomplete-and-mostly-wrong.html
        Amusing "history" of computer science.
        \_ Where's the mentioning of Al Gore the inventor of AlGorithm?
	...
2011/6/29-7/21 [Computer/SW/Database, Computer/SW] UID:54133 Activity:nil
6/29    "An Israeli algorithm sheds light on the Bible"
        http://www.csua.org/u/tq4 (news.yahoo.com)
        "Software developed by an Israeli team is giving intriguing new hints
        about what researchers believe to be the multiple hands that wrote the
        Bible."
        \_ "Hype developed by an American OnLine News Feed is giving
	...
2010/8/9-19 [Computer/SW/Security] UID:53917 Activity:nil
8/9     I got two files, one is size 522190848 and the other is size
        521648128.  Both sha256 to the same number.  (and sha1 too).
        I don't think this is supposed to happen, right? (least not with
        sha256).
        \_ how are you checking?
           \_ I burned one file to cd, so i mounted /cdrom and
	...
2010/1/20-29 [Computer/SW/Languages/Misc, Computer/SW/Security] UID:53649 Activity:nil
1/20    Did Chinese come up with new way of quicksort?
        http://www.nytimes.com/2010/01/20/technology/20cyber.html
        Joe Stewart, a malware specialist with SecureWorks, a computer
        security company based in Atlanta, said he determined the main
        program used in the attack contained a module based on an unusu
        al algorithm from a Chinese technical paper that has been
	...
2009/10/24-11/3 [Computer/HW/Laptop] UID:53466 Activity:kinda low
10/24   How well do you see color? I got 8, how about you?
        http://www.xrite.com/custom_page.aspx?PageID=77
        \_ 7
           \_ what monitor did you use?
              \_ LCD on thinkpad x32, under not so great lighting conditions.
        \_ I scored 101, which seems impossible. Then again, I didn't
	...
2009/1/13-22 [Computer/Theory] UID:52367 Activity:kinda low
1/13    I am writing a commandline parser for a class and I could use some
        tips for algorithms to use. (The project is over and done so I am
        not cheating, but I am dissatisfied with my end result.) I STFW and
        didn't come up with too much I liked. I read the source for some
        shells like tcsh and that is *WAY* too complicated and relies on
        a lot of other code. I know that browsers and other apps have
	...
2008/12/2-6 [Computer/SW/Apps, Academia/Berkeley/CSUA/Motd] UID:52140 Activity:kinda low
12/1    Just curious -- what do you guys generally use soda for? Why do you
        log on? Personally, I use it to keep a presence on IRC and AIM/gTalk
        at all times, and mess around with some Python programming (been
        setting up Twisted and such so I can play with making an irc bot).
        --toulouse
        \_ I use it to post SHIT, er, I mean, spill my guts about the company
	...
2008/11/25-28 [Computer/Theory] UID:52108 Activity:nil
11/25   Holy crap! I was the one asking how to open a locked up masterlock a
        few days ago. I tried the algorithm on this webpage:
        http://www.wikihow.com/Crack-a-%22Master-Lock%22-Combination-Lock
        and it worked! Thanks to whoever suggested it.
        \_ Good to know, thanks for the reply.
	...
Cache (8192 bytes)
www.mapleapps.com/categories/mathematics/algebra/html/FFT-Polynomial.html
An Analogy * A Series of Needed Procedures * Initial Data * The Traditional Multiplication of Two Polynomials * Explanation of the DFT/FFT Method * List Padding as Preparation for DFT/FFT * 8 The DFT Approach * The FFT Approach * 10 Time Comparisons * 11 References POLYNOMIALS MULTIPLICATION USING THE FAST FOURIER TRANSFORM Bruno Guerrieri Florida A&M University We will be multiplying polynomials using two different ways, (traditional and FFT), and see whether one method is consistently faster than the other one. We will let the polynomials A(x) and B(x) be of the same degree for simplicity and we will generate the polynomials coefficients randomly. For a more detailed explanation of what follows, please consult in the Reference section. An Analogy Consider the following table: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8182 16384 32768 You have, of course, noticed that entry i in row 1 corresponds to entry 2^i in row 2. Or, to put it another way, the top row lists the logarithms in base 2 of the bottom list. What if we wanted to calculate (64)(512)? One way would be to follow the traditional algorithm that we all learned in grammar school and perform the standard multiplication. The other way would be to locate the corresponding logarithms, namely 6 and 9, ADD these two logarithms to get 15, and then determine the antilog, our answer, namely 32768. In what follows, the strategy is the same. The quantities "worked on" and the operations are different. Instead of multiplying numbers, we will be multiplying polynomials. The equivalent of taking logarithms and antilogarithms will be polynomial evaluations and interpolations and the equivalent of our ADD will be POINTWISE multiplication. RETURN(c); The procedure "padding" "right-pads" a list of coefficients with "deg" zeros. RETURN(d); Vector "c" is obtained by "convolving" the input coefficients vectors "a" and "b". RETURN(c); The procedure "dft" (Discrete Fourier Transform) is present here since we wanted to, in fact compare the three processes for multiplication of two polynomials, namely the traditional, DFT, and FFT (Fast Fourier Transform) processes. One has to get into high degrees to see the FFT overtake the traditional method. The DFT is present here to make us appreciate the speed improvement that the FFT brings to the situation. The procedure "dft" which follows takes two arguments. The first one is the list to be transformed. The second argument is set so that a = 1 for DFT and a = -1 for IDFT (Inverse Discrete Fourier Transform). The last part of the code takes very small values (usually on the inverse transformation when dealing with original real data) located in the imaginary part and zero them out. So first the list is "split" into real and imaginary parts, Fourier transformation occurs, zeroing out is done where needed, and then the two lists are "sewn" back together. LS1 := nops(h_in); LS1 do > sum1 := 0; LS1 do > sum1 := sum1 + h_in *exp(a*I*2*Pi*(j-1)*(k-1)/LS1); RETURN(h_out); The FFT/IFFT procedure call is to be found below. The only reason the procedure shown below looks lengthy is because real part and imaginary part of lists going through the FFT or the IFFT have to be kept separated. LS1,nombre,re_list,im_list,re_array,im_array,L_out; LS1 := nops(L_in); FFT(nombre,re_array,im_array) else iFFT(nombre,re_array,im_array); L_out := zip((a,b)->simplify((a+b*I)),re_list,im_list); RETURN(L_out); The "power_of_two" procedure determines the nearest power greater than deg(A(x)) + deg(B(x) + 1. This is needed, for padding purposes, since the FFT/IFFT needs "power of two" list sizes. RETURN(2^i); The " zeros_plot" procedure "reconstructs" a polynomial from its coefficients so that its zeros can be determined and plotted if necessary. N := nops(coef_list); N do > y := y + coef_list *x^(i-1); R := fsolve(y,x,complex) ; Re(z),Im(z) ,R); RETURN(p); Initial Data Now that all the procedures we will need have been written, let us randomly generate the "deg+1" coefficients of two polynomials A(x) and B(x) of degree "deg". For simplicity, we will take the two polynomials to be of the same degree. Otherwise, we would have to pad with zeros. We are saving these two lists, in c_list and d_list, so that we can use the same polynomials with the DFT and then the FFT approaches. The Traditional Multiplication of Two Polynomials In the straightforward multiplication (convolution) method that follows, list sizes are handled automatically. We will notice, when we use the DFT approach that the padding will always be up to a power of 2. The final answer provides a list of the coefficients of the resulting polynomials C(x). Explanation of the DFT/FFT Method Again, for a more detailed explanation we recommend that you refer to . We would like to multiply the same two polynomials seen above using the DFT. Very quickly, we will come to realize that this process requires a lot of computing time. In fact the DFT is no match for the traditional method. We wanted to investigate the DFT approach for the simple reason that it is a routine that you can write on your own by using the definition for the DFT. This way, anybody unfamiliar with the intricacies of the FFT, can feel somewhat at ease when told that the FFT is nothing but a "souped up" DFT - (Apologies to Cooley and Tukey ). Therefore we recommend that you bypass the DFT process and go directly to the FFT one whenever your polynomial degrees start to get above 50. Note that the polynomial representation we used above, where polynomials are identified by their coefficient lists, is called the "coefficient representation (CR)". One can also use the "point-value representation (PVR)". While multiplying polynomials in CR form takes O( n^2 ), the alternative multiplicative option of using the three steps of a) conversion to PVR, b) pointwise multiplication, c) reconversion to CR only takes O( n*log(n) ). The evaluation of a polynomial at a particular value of x is usually carried out using Horner's method. PVR form by relying on Lagrange polynomials. Thus n -points evaluation and interpolation are therefore well-defined operations that allow one to move from CR to PVR and back again. Let us assume in the rest of the discussion that n = deg( A(x) = deg( B(x) ). Since the resulting polynomial is of degree 2*n , we must start with "extended" 2*n+1 PVR form for both polynomials A and B. The quantity (+ 1 ) that appears at times has to do with the fact that a polynomial of degree n has n+1 coefficients. We must also, since the FFT is at its best when processing lists whose lengths are powers of 2, let 2 n be a power of 2. Be aware that there are two sorts of padding going on. One was seen at work in the traditional multiplication process. But the one we are referring to now has to do with bringing all lists to lengths that are powers of 2. One can be clever in the choice of the x 's (there will be 2 n of them) at which polynomials will be evaluated so as to determine the corresponding PVR form. In fact, if we choose "complex roots of unity" as evaluation points, we can produce a PVR form of a given polynomial in CR form by taking the DFT of the coefficient vector. IDFT takes care of interpolation so as to bring us back to a CR form, from a PVR form. Here is the algorithm we will be following : Start with A(x) and B(x) in coefficient (CR) form. Create coefficient representation of A(x) and B(x) as polynomials of degree 2 n . Time = O( n ) . Evaluate: Compute point-value representation of A(x) and B(x) of length 2*n through applications of the DFT (later the FFT) of order 2*n to each coefficient vector. These representations contains the values of the two polynomials at the ( 2*n )th roots of unity. Time = O( nlog(n) ) . The representation obtained contains the value of C(x) at each ( 2*n )th roots of unity. Time = O( n ) . Interpolate: Create the coefficient representation of the polynomial C(x) through a single application of a IDFT (later IFFT) on 2*n point-value pairs. Time = O( nlog(n) ) . What has been done is as follows: {a} convolved with {b} = IDFT DFT(a)*DFT(b) , where vectors {a} and {b} have been padded wi...