From rfb.cam.nist.gov!boisvert Thu May 10 06:53:02 PDT 1990 Received: by pyxis; Thu May 10 09:50 EDT 1990 To: pyxis!ehg Received: by inet.att.com; Thu May 10 09:50 EDT 1990 Received: by patience.stanford.edu (4.0/inc-1.5) id AA12311; Thu, 10 May 90 06:53:02 PDT Date: Thu, 10 May 90 06:53:02 PDT From: boisvert@rfb.cam.nist.gov Message-Id: <9005101353.AA12311@patience.stanford.edu> Apparently-To: ehg@research.att.com >From boisvert@rfb.cam.nist.gov Thu May 10 06:52:53 1990 Received: from fs1.cam.nist.gov ([129.6.80.33]) by patience.stanford.edu (4.0/inc-1.5) id AA12284; Thu, 10 May 90 06:52:53 PDT Received: from rfb.cam.nist.gov by fs1.cam.nist.gov (4.1/SMI-DDN) id AA27410; Thu, 10 May 90 09:52:52 EDT Received: by rfb.cam.nist.gov (4.1/SMI-3.2) id AA02029; Thu, 10 May 90 09:47:38 EDT Date: Thu, 10 May 90 09:47:38 EDT From: boisvert@rfb.cam.nist.gov (Ronald Boisvert) Message-Id: <9005101347.AA02029@rfb.cam.nist.gov> To: na.grosse@na-net.stanford.edu Subject: netlib contribution Several years ago Roland Sweet and I developed a vectorized version of FFTPKG for transforming multiple real sequences. We would like to contribute it to netlib. There are 27 subroutines in the package plus one summary documentation file; there are 2873 lines in all. The package is in standard Fortran and has been run successfully on many systems including Sun3, Sun4, Vax VMS, Cyber NOS, Cyber NOS/VE, Cyber 205, Convex, and others. I attach the summary documentation file which is probably suitable for a "send index for vfftpk". If you are interested I would be happy to email the who package to you. I would be happy to do any other tasks required for netlib submission. - Ron ---------------------------------------------------------------------- * * * * * * * * * * * * * * * * * VFFTPK * * * * * * * * * * * * * * * * * (Version 2.1 May 1990) A vectorized package of Fortran subprograms for the fast Fourier transform of multiple real sequences by Roland A. Sweet and Linda L. Lindgren Center for Computing and Applied Mathematics National Institute of Standards and Technology Boulder, Colorado 80303 Ronald F. Boisvert Center for Computing and Applied Mathematics National Institute of Standards and Technology Gaithersburg, Maryland 20899 * * * * * * * * * * * * * * * * * Background * * * * * * * * * * * * * * * * * NOTATION -------- To simulate the mathematical symbol 'sigma' that represents summation, we define the notation SUM(l=is,if)[ y(l) ] = y(is) + y(is+1) + . . . + y(if) . DISCRETE FOURIER TRANSFORM -------------------------- Given a complex periodic sequence x(j), j=0,1,...,n-1, the discrete Fourier transform is defined by x(j) = sqrt(1/n)*SUM(k=0,n-1)[ f(k)*exp(2j*k*i*pi/n) ] , for j = 0, 1, . . . , n-1 , where i = sqrt(-1). The discrete Fourier coefficients, f(k), are given by f(k) = sqrt(1/n)*SUM(j=0,n-1)[ x(j)*exp(-2j*k*i*pi/n) ] , for k = 0, 1, . . . , n-1 . REAL PERIODIC TRANSFORM ----------------------- To facilitate the following discussion we define the integer m by m = n/2 when n is even, and m = (n+1)/2 when n is odd. If the given sequence x(j) is real, the Fourier coefficients are conjugate symmetric, i.e. f(n-k) is equal to the complex conjugate of f(k). This relation implies that the sequence x(j) can be completely determined from the n real quantities real(f(0)) = sqrt(1/n)*SUM(j=0,n-1)[ x(j) ], real(f(k)) = sqrt(1/n)*SUM(j=0,n-1)[ x(j)*cos(2j*k*pi/n) ] imag(f(k)) = -sqrt(1/n)*SUM(j=0,n-1)[ x(j)*sin(2j*k*pi/n) ] for k = 1, 2, . . . , m-1, and, when n is even, real(f(n/2)) = sqrt(1/n)*SUM(j=0,n-1)[ (-1)**j*x(j) ]. TRIGONOMETRIC REPRESENTATION ---------------------------- When the sequence x(j) is real the discrete Fourier transform may be re-written as the trigonometric series x(j) = sqrt(2/n)* c(0)/2 + (-1)**j*c(n-1)/2 + SUM(k=1,m-1) [c(2k-1)*cos(2j*k*pi/n) + c(2k)*sin(2j*k*pi/n)] when n is an even integer (n = 2*m), or as x(j) = sqrt(2/n)* c(0)/2 + SUM(k=1,m-1) [c(2k-1)*cos(2j*k*pi/n) + c(2k)*sin(2j*k*pi/n)] when n is an odd integer (n = 2*m-1), for j = 0, 1, . . . , n-1 . The coefficients c(k) are defined by the relations c(0) = sqrt(2/n)*SUM(j=0,n-1)[ x(j) ] for k = 1, 2, . . . , m-1 , c(2*k-1) = sqrt(2/n)*SUM(j=0,n-1)[ x(j)*cos(2j*k*pi/n) ] c(2*k) = sqrt(2/n)*SUM(j=0,n-1)[ x(j)*sin(2j*k*pi/n) ] and, when n is even c(n-1) = sqrt(2/n)*SUM(j=0,n-1)[ (-1)**j*x(j) ] . The relationship between the coefficients c(k) and the conjugate symmetric Fourier coefficients f(k) is c(0) = sqrt(2)*f(0) , c(2*k-1) = sqrt(2)*real(f(k)) and c(2*k) = -sqrt(2)*imag(f(k)) for k = 1, 2, . . . , m-1, and when n is even c(n-1) = sqrt(2)*f(n/2) . SINE TRANSFORM OF AN ODD SEQUENCE --------------------------------- Let x(k) be a real odd sequence, that is, it can be expanded in terms of a trigonometric series that contains only sine terms. The discrete odd Fourier transform is given by c(k) = SUM(j=1,n-1)[ 2x(j)*sin(j*k*pi/n) ]/sqrt(2n). for k = 1, 2, . . ., n-1. The inverse transform is identical, that is, x(k) = SUM(j=1,n-1)[ 2c(j)*sin(j*k*pi/n) ]/sqrt(2n) for k = 1, 2, . . ., n-1. COSINE TRANSFORM OF AN EVEN SEQUENCE ------------------------------------ Let x(k) be a real even sequence, that is, it can be expanded in terms of a trigonometric series that contains only cosine terms. The discrete even Fourier transform is given by c(k) = ( x(0) + (-1)**k*x(n) + SUM(j=1,n-1)[ 2x(j)*cos(j*k*pi/n) ] )/sqrt(2n) for k = 0, 1, 2, . . ., n. The inverse transform is identical, that is, x(k) = ( c(0) + (-1)**k*c(n) + SUM(j=1,n-1)[ 2c(j)*cos(j*k*pi/n) ] )/sqrt(2n) for k = 0, 1, 2, . . ., n. QUARTER-WAVE COSINE TRANSFORM ----------------------------- Let x(k) be a real even quarter-wave sequence, that is, it can be expanded in terms of a cosine series with only odd wave numbers. The discrete cosine quarter-wave Fourier transform is given by c(k) = ( x(1) + SUM(j=2,n)[ 2x(j)*cos((j-1)*(2k-1)*pi/2n) ] )/sqrt(4n) for k = 1, 2, . . ., n. The inverse transform is given by x(k) = SUM(j=1,n)[ 4c(j)*cos((2j-1)*(k-1)*pi/2n) ]/sqrt(4n) for k = 1, 2, . . ., n. QUARTER-WAVE SINE TRANSFORM --------------------------- Let x(k) be a real odd quarter-wave sequence; that is, it can be expanded in terms of a sine series with only odd wave numbers. The discrete quarter-wave sine transform is given by c(k) = ( SUM(j=1,n-1)[ 2x(j)*sin(j*(2k-1)*pi/2n) ] + (-1)**(k-1)*x(n) )/sqrt(4n) for k = 1, 2, . . ., n. The inverse transform is given by x(k) = ( SUM(j=1,n) [ 4c(j)*sin((2j-1)*k*pi/2n) ] )/sqrt(4n) for k = 1, 2, . . ., n. * * * * * * * * * * * * * * * * * * * * * * * * Description of Package * * * * * * * * * * * * * * * * * * * * * * * * This package consists of subroutines that compute the transforms between sequences x(j) and the Fourier coefficients f(k) described above for multiple real sequences. The real periodic transform is a variant of the Stockham autosort algorithm. There is no restriction on the length of the sequence. The other specialized transforms are implemented by preprocessing and postprocessing. In the description below we use the following terms: forward transform = Fourier analysis. Computation of Fourier coefficients f(k) from the sequence x(k). backward transform = Fourier synthesis. Computation of the sequence x(k) from its Fourier coefficients f(k). The user-callable subroutines are : 1. VRFFTI Initialization routine for VRFFTF and VRFFTB 2. VRFFTF Forward transform of multiple real periodic sequences 3. VRFFTB Backward transform for multiple real periodic sequences 4. VSINTI Initialization routine for VSINT 5. VSINT Forward or backward transform for multiple odd sequences 6. VCOSTI Initialization routine for VCOST 7. VCOST Forward or backward transform for multiple even sequences 8. VSINQI Initialization routine for VSINQF and VSINQB 9. VSINQF Forward transform of multiple odd sequences with only odd wave numbers (quarter-wave sine transform) 10. VSINQB Backward transform for multiple odd sequences with only odd wave numbers (quarter-wave sine transform) 11 VCOSQI Initialization routine for VCOSQF and VCOSQB 12 VCOSQF Forward transform of multiple even sequences with only odd wave numbers (quarter-wave cosine transform) 13. VCOSQB Backward transform of multiple even sequences with only odd wave numbers (quarter-wave cosine transform) This package is a straightforward vectorization of the scalar package FFTPACK (Version 3, June 1979) written by Paul N. Swarztrauber of the National Center for Atmospheric Research, Boulder, Colorado, 80307. All vector lengths are equal to the number of sequences being transformed. One slight change has been made: symmetric scaling has been incorporated into the forward and backward transforms. Revision history: Version 1.0 (Aug 1985) : VRFFTF, VRFFTB, VRFFTI developed by Sweet and Lindgren Version 2.0 (Mar 1987) : VSINT, VSINTI, VCOST, VCOSTI, VSINQF, VSINQB, VSINQI, VCOSQF, VCOSQB, VCOSQI added by Boisvert Version 2.1 (May 1990) : documentation revised From rfb.cam.nist.gov!boisvert Thu May 10 10:17:09 EDT 1990 Received: by pyxis; Thu May 10 10:17 EDT 1990 Received: by inet.att.com; Thu May 10 10:17 EDT 1990 Received: from rfb.cam.nist.gov by fs1.cam.nist.gov (4.1/SMI-DDN) id AA27602; Thu, 10 May 90 10:22:03 EDT Received: by rfb.cam.nist.gov (4.1/SMI-3.2) id AA02141; Thu, 10 May 90 10:17:09 EDT Date: Thu, 10 May 90 10:17:09 EDT From: boisvert@rfb.cam.nist.gov (Ronald Boisvert) Message-Id: <9005101417.AA02141@rfb.cam.nist.gov> To: ehg@research.att.com Subject: Here is vfftpk From rfb.cam.nist.gov!boisvert Thu May 10 10:20:14 EDT 1990 Received: by pyxis; Thu May 10 10:20 EDT 1990 Received: by inet.att.com; Thu May 10 10:20 EDT 1990 Received: from rfb.cam.nist.gov by fs1.cam.nist.gov (4.1/SMI-DDN) id AA27645; Thu, 10 May 90 10:25:13 EDT Received: by rfb.cam.nist.gov (4.1/SMI-3.2) id AA02152; Thu, 10 May 90 10:20:14 EDT Date: Thu, 10 May 90 10:20:14 EDT From: boisvert@rfb.cam.nist.gov (Ronald Boisvert) Message-Id: <9005101420.AA02152@rfb.cam.nist.gov> To: ehg@research.att.com Subject: wc for vfftpk 2596 9631 86500 ------m rfb.cam.nist.gov!boisvert Thu May 10 10:36:03 EDT 1990 From-: Eric Grosse ehg@research.att.com 201-582-5828 To-: rfb.cam.nist.gov!boisvert Date-: Thu May 10 10:34:53 EDT 1990 Subject: vfftpk Ok, it's installed here. It will go out to the other sites (ORNL, Oslo, Australia) in the next update, probably a week or two from now. Many thanks for the contribution! Best wishes Eric ------m na.swarztrauber@na-net.stanford.edu Thu May 10 10:45:35 EDT 1990 From-: Eric Grosse ehg@research.att.com 201-582-5828 To-: na.swarztrauber@na-net.stanford.edu Date-: Thu May 10 10:45:27 EDT 1990 Subject: vfftpk Ron Boisvert just contributed vfftpk to netlib. This looks like a nice supplement to your FFTPACK (and the index gives you proper credit). I make a point of trying to always contact original code authors to be sure there are no misunderstandings. You're happy with vfftpk, I assume? If you do have any concerns, please let me know before this gets widely distributed. Best wishes Eric ------m na.sweet@na-net.stanford.edu Thu May 10 10:47:40 EDT 1990 From-: Eric Grosse ehg@research.att.com 201-582-5828 To-: na.sweet@na-net.stanford.edu Date-: Thu May 10 10:46:26 EDT 1990 Subject: vfftpk Ron Boisvert just contributed vfftpk to netlib. This looks like a nice supplement to FFTPACK and I'm delighted to get it. I make a point of trying to always contact original code authors to be sure there are no misunderstandings. You're happy with vfftpk, I assume? If you do have any concerns, please let me know before this gets widely distributed. Best wishes Eric From copper.Denver.Colorado.EDU!rsweet Thu May 10 11:03:51 MDT 1990 Received: by pyxis; Thu May 10 13:35 EDT 1990 Received: by inet.att.com; Thu May 10 13:35 EDT 1990 Received: by pikes.Denver.Colorado.EDU (cudenver.ether) Received: by copper.Denver.Colorado.EDU (cudenver.ether) Date: Thu, 10 May 90 11:03:51 mdt From: rsweet@copper.Denver.Colorado.EDU (Sweet Roland) Message-Id: <9005101703.AA07582@copper.Denver.Colorado.EDU> To: ehg@research.att.com Subject: re: vfftpk I have no objections. Ron and I talked about it recently. I am happy with the package. Roland From bierstadt.scd.ucar.EDU!pauls Mon May 14 14:25:35 MDT 1990 Received: by pyxis; Mon May 14 16:25 EDT 1990 Received: by inet.att.com; Mon May 14 16:25 EDT 1990 Received: from bierstadt.scd.ucar.edu by ncar.ucar.EDU (5.61/ NCAR Central Post Office 04/10/90) id AA00934; Mon, 14 May 90 14:25:41 MDT From: pauls@bierstadt.scd.ucar.EDU (Paul Swarztrauber) Received: from silver.scd.ucar.edu by bierstadt.scd.ucar.EDU (5.61/ NCAR Mail Server 04/10/90) id AA18276; Mon, 14 May 90 14:25:38 MDT Date: Mon, 14 May 90 14:25:35 MDT Message-Id: <9005142025.AA00235@silver.scd.ucar.edu> Received: by silver.scd.ucar.edu (5.61/ NCAR Mail Client 04/10/90) id AA00235; Mon, 14 May 90 14:25:35 MDT To: ehg@research.att.com I vagely remember something about vfftpk but not enough to express an opinion. If its a vector version of FFTPACK then it is needed but I do not have any experience with it. Thanks for the info Paul .