Multidimensional pseudo-spectral methods on lattice grids

When multidimensional functions are approximated by a truncated Fourier series, the number of terms typically increases exponentially with the dimension s. However, for functions with more structure than just being L²-integrable, the contributions from many of the Ns terms in the truncated Fourier series may be insignificant. In this paper we suggest a way to reduce the number of terms by omitting the insignificant ones. We then show how lattice rules can be used for approximating the associated Fourier coefficients, allowing a similar reduction in grid points as in expansion terms. We also show that using a lattice grid permits the efficient computation of the Fourier coefficients by the FFT algorithm. Finally we assemble these ideas into a pseudo-spectral algorithm and demonstrate its efficiency on the Poisson equation.     

Numerical evaluation of finite Fourier integrals

A computationally efficient algorithm for evaluating Fourier integrals ∫¹_?1?(x)e^iωxdx using interpolatory quadrature formulas on any set of collocation points is presented. Examples are given to illustrate the performances of interpolatory formulas which are based on the applications of the Fejér, Clenshaw—Curtis, Basu and the Newton—Cotes points. Initially, the formulas for nonoscillatory integrals are generated and then generalizations to finite Fourier integrals are made. Extensions of this algorithm to some other weighted integrals are also considered.     

Factoring Polynomials and the Knapsack Problem

For several decades the standard algorithm for factoring polynomials f with rational coefficients has been the Berlekamp-Zassenhaus algorithm. The complexity of this algorithm depends exponentially on n, where n is the number of modular factors of f. This exponential time complexity is due to a combinatorial problem: the problem of choosing the right subsets of these n factors. In this paper, this combinatorial problem is reduced to a type of Knapsack problem that can be solved with lattice reduction algorithms. The result is a practical algorithm that can factor polynomials that are far out of reach for previous algorithms. The presented solution to the combinatorial problem is different from previous lattice-based factorizers; these algorithms avoided the combinatorial problem by solving the entire factorization problem with lattice reduction. This led to lattices of large dimension and coefficients, and thus poor performance. This is why lattice-based algorithms, despite their polynomial time complexity, did not replace Berlekamp-Zassenhaus as the standard method. That is now changing; new versions of computer algebra systems such as Maple, Magma, NTL and Pari have already switched to the algorithm presented here.     

A summability method for the arithmetic Fourier transform

The Arithmetic Fourier Transform (AFT) is an algorithm for the computation of Fourier coefficients, which is suitable for parallel processing and in which there are no multiplications by complex exponentials. This is accomplished by the use of the Möbius function and Möbius inversion. However, the algorithm does require the evaluation of the function at an array of irregularly spaced points. In the case that the function has been sampled at regularly spaced points, interpolation is used at the intermediate points of the array. Generally theAFT is most effective when used to calculate the Fourier cosine coefficients of an even function.In this paper a summability method is used to derive a modification of theAFT algorithm. The proof of the modification is quite independent of theAFT itself and involves a summation by primes. One advantage of the new algorithm is that with a suitable sampling scheme low order Fourier coefficients may be calculated without interpolation.     

A local Paley-Wiener theorem for compact symmetric spaces

The Fourier coefficients of a smooth K-invariant function on a compact symmetric space M=U/K are given by integration of the function against the spherical functions. For functions with support in a neighborhood of the origin, we describe the size of the support by means of the exponential type of a holomorphic extension of the Fourier coefficients.     

An automatic augmented galerkin method for singular integral equations with Hilbert kernel

In [1, 2], described a Chebyshev series method for the numerical solution of integral equations with three automatic algorithms for computing two regularization parameters,C _f andr. Here we describe a Fourier series expansion method for a class of singular integral equations with Hilbert kernel and constant coefficients with using a new automatic algorithm.     

On Dirichlet <Emphasis Type="Italic">L</Emphasis>-functions with periodic coefficients and Eisenstein series

We prove a Lipschitz type summation formula with periodic coefficients. Using this formula, representations of the values at positive integers of Dirichlet L-functions with periodic coefficients are obtained in terms of Bernoulli numbers and certain sums involving essentially the discrete Fourier transform of the periodic function forming the coefficients. The non-vanishing of these L-functions at s = 1 are then investigated. There are additional applications to the Fourier expansions of Eisenstein series over congruence subgroups of \({SL_2(\mathbb{Z})}\) and derivatives of such Eisenstein series. Examples of a family of Eisenstein series with a high frequency of vanishing Fourier coefficients are given.     

Absolutely convergent Fourier series and function classes

We study the smoothness property of a function f with absolutely convergent Fourier series, and give best possible sufficient conditions in terms of its Fourier coefficients to ensure that f belongs either to one of the Lipschitz classes Lip(α) and lip(α) for some 0<α?1, or to one of the Zygmund classes Λ_∗(1) and λ_∗(1). Our theorems generalize some of those by Boas [R.P. Boas Jr., Fourier series with positive coefficients, J. Math. Anal. Appl. 17 (1967) 463-483] and one by Németh [J. Németh, Fourier series with positive coefficients and generalized Lipschitz classes, Acta Sci. Math. (Szeged) 54 (1990) 291-304]. We also prove a localized version of a theorem by Paley [R.E.A.C. Paley, On Fourier series with positive coefficients, J. London Math. Soc. 7 (1932) 205-208] on the existence and continuity of the derivative of f.     

О сходимости в метрике L четных тригонометрических интерполяционных полиномов по равноотстояшим уэлам

Even, 2π-periodic, continuous for all x ≠ 2πn, n = 0, 1, …, functions, represented by Fourier series are considered. The question of convergence in the metric L of the trigonometric interpolation cosine polinomials of such functions with convex, quasiconvex, monotone and quasimonotone Fourier coefficients is investigated.     

Free and forced vibrations of trusses by Fourier decomposition, and homotopy methods for nonlinear matrix eigenvalue problems: (I) Methods

Vibrations of elastic frames or trusses are investigated by use of Fourier/frequency domain methods, using classical solutions of linear hyperbolic PDEs with constant coefficients and angle-preserving connections of beams (by clamping). Separation of variables is used, e.g., A(x,μ)e^μt. For free vibrations, eigensolutions (in particular their values μ=α+iβ) are determined homotopically and individually, employing systems of quasilinear ODEs, usually explicit. Additionally to the methods in Part (I), properties and supplements are presented in Part (II).     

Chirp transforms and Chirp series

Motivated by the recent work on the non-harmonic Fourier atoms initiated by T. Qian and the non-harmonic Fourier series which originated from the celebrated work of Paley and Wiener, we introduce an integral version of the non-harmonic Fourier series, called Chirp transform. As an integral transform with kernel ei?(t)θ(ω), the Chirp transform is an unitary isometry from L²(R,d?) onto L²(R,dθ) and it can be explicitly defined in terms of generalized Hermite polynomials. The corresponding Chirp series take einθ(t) as a basis which in some sense is dual to the theory of non-harmonic Fourier series which take eiλnt as a basis. The Chirp version of the Shannon sampling theorem and the Poisson summation formula are also considered by dealing with sampling points which may non-equally distributed. Since the Chirp transform interchanges weighted derivatives into multiplications, it plays a role in solving certain differential equations with variable coefficients. In addition, we extend T. Qian's theorem on the characterization of a measure to be a linear combination of a number of harmonic measures on the unit disc with positive integer coefficients to that with positive rational coefficients.     

Siegel cusp forms of degree 2 are determined by their fundamental Fourier coefficients

We prove that a Siegel cusp form of degree 2 for the full modular group is determined by its set of Fourier coefficients a(S) with 4 det(S) ranging over odd squarefree integers. As a key step to our result, we also prove that a classical cusp form of half-integral weight and level 4N, with N odd and squarefree, is determined by its set of Fourier coefficients a(d) with d ranging over odd squarefree integers, a result that was previously known only for Hecke eigenforms.     

A kernel for automorphic L-functions

The full multiple Dirichlet series of an automorphic cusp form is defined, in classical language, as a Dirichlet series of several complex variables over all the Fourier coefficients of the cusp form. It is different from the L-function of Godement and Jacquet, which is defined as a Dirichlet series in one complex variable over a one-dimensional array of the Fourier coefficients. In GL(2) and GL(3), the two notions are simply related. In this paper, we construct a kernel function that gives the full multiple Dirichlet series of automorphic cusp forms on GL(n,R). The kernel function is a new Poincaré series. Specifically, the inner product of a cusp form with this Poincaré series is the product of the full multiple Dirichlet series of the form times a function that is essentially the Mellin transform of Jacquet's Whittaker function. In the proof, the full multiple Dirichlet series is produced by applying the Lipschitz summation formula several times and by an integral which collapses the sum over SL(n−1,Z) in the Fourier expansion of the cusp form.     

The polyharmonic local sine transform: A new tool for local image analysis and synthesis without edge effect

We introduce a new local sine transform that can completely localize image information both in the space domain and in the spatial frequency domain. This transform, which we shall call the polyharmonic local sine transform (PHLST), first segments an image into local pieces using the characteristic functions, then decomposes each piece into two components: the polyharmonic component and the residual. The polyharmonic component is obtained by solving the elliptic boundary value problem associated with the so-called polyharmonic equation (e.g., Laplace's equation, biharmonic equation, etc.) given the boundary values (the pixel values along the boundary created by the characteristic function). Subsequently this component is subtracted from the original local piece to obtain the residual. Since the boundary values of the residual vanish, its Fourier sine series expansion has quickly decaying coefficients. Consequently, PHLST can distinguish intrinsic singularities in the data from the artificial discontinuities created by the local windowing. Combining this ability with the quickly decaying coefficients of the residuals, PHLST is also effective for image approximation, which we demonstrate using both synthetic and real images. In addition, we introduce the polyharmonic local Fourier transform (PHLFT) by replacing the Fourier sine series above by the complex Fourier series. With a slight sacrifice of the decay rate of the expansion coefficients, PHLFT allows one to compute local Fourier magnitudes and phases without revealing the edge effect (or Gibbs phenomenon), yet is invertible and useful for various filtering, analysis, and approximation purposes.     

Numerical computation of the fourier transform using Laguerre functions and the Fast Fourier Transform

Summary In this paper we propose a numerical technique for the computation of Fourier transforms. It uses a bilateral expansion of the unknown transformed function with respect to Laguarre functions. The expansion coefficients are obtained via trigonometric interpolation and may be computed very efficiently by means of the Fast Fourier Transform. The convergence of the algorithm is analyzed and numerical results are presented which confirm that it works well.     

An exact algorithm for large multiple knapsack problems

The Multiple Knapsack Problem (MKP) is the problem of assigning a subset of n items to m distinct knapsacks, such that the total profit sum of the selected items is maximized, without exceeding the capacity of each of the knapsacks. The problem has several applications in naval as well as financial management. A new exact algorithm for the MKP is presented, which is specially designed for solving large problem instances. The recursive branch-and-bound algorithm applies surrogate relaxation for deriving upper bounds, while lower bounds are obtained by splitting the surrogate solution into the m knapsacks by solving a series of Subset-sum Problems. A new separable dynamic programming algorithm is presented for the solution of Subset-sum Problems, and we also use this algorithm for tightening the capacity constraints in order to obtain better upper bounds. The developed algorithm is compared to the mtm algorithm by Martello and Toth, showing the benefits of the new approach. A surprising result is that large instances with n=100 000 items may be solved in less than a second, and the algorithm has a stable performance even for instances with coefficients in a moderately large range.     

Exact Fourier expansion in cylindrical coordinates for the three-dimensional Helmholtz Green function

A new method is presented for Fourier decomposition of the Helmholtz Green function in cylindrical coordinates, which is equivalent to obtaining the solution of the Helmholtz equation for a general ring source. The Fourier coefficients of the Green function are split into their half advanced + half retarded and half advanced–half retarded components, and closed form solutions for these components are then obtained in terms of a Horn function and a Kampé de Fériet function respectively. Series solutions for the Fourier coefficients are given in terms of associated Legendre functions, Bessel and Hankel functions and a hypergeometric function. These series are derived either from the closed form 2-dimensional hypergeometric solutions or from an integral representation, or from both. A simple closed form far-field solution for the general Fourier coefficient is derived from the Hankel series. Numerical calculations comparing different methods of calculating the Fourier coefficients are presented. Fourth order ordinary differential equations for the Fourier coefficients are also given and discussed briefly.     

A Levin-type algorithm for accelerating the convergence of Fourier series

A nonlinear sequence transformation is presented which is able to accelerate the convergence of Fourier series. It is tailored to be exact for a certain model sequence. As in the case of the Levin transformation and other transformations of Levin-type, in this model sequence the partial sum of the series is written as the sum of the limit (or antilimit) and a certain remainder, i.e., it is of Levin-type. The remainder is assumed to be the product of a remainder estimate and the sum of the first terms oftwo Poincaré-type expansions which are premultiplied by two different phase factors. This occurrence of two phase factors is the essential difference to the Levin transformation. The model sequence for the new transformation may also be regarded as a special case of a model sequence based on several remainder estimates leading to the generalized Richardson extrapolation process introduced by Sidi. An algorithm for the recursive computation of the new transformation is presented. This algorithm can be implemented using only two one-dimensional arrays. It is proved that the sequence transformation is exact for Fourier series of geometric type which have coefficients proportional to the powers of a numberq, |q|<1. It is shown that under certain conditions the algorithm indeed accelerates convergence, and the order of the convergence is estimated. Finally, numerical test data are presented which show that in many cases the new sequence transformation is more powerful than Wynn's epsilon algorithm if the remainder estimates are properly chosen. However, it should be noted that in the vicinity of singularities of the Fourier series the new sequence transformation shows a larger tendency to numerical instability than the epsilon algorithm.     

On convergence of odd trigonometric interpolation polynomials with equidistant points in the metric <Emphasis Type="Italic">L</Emphasis>

Odd, 2π-periodical, continuous functions represented by Fourier series are considered. The question of the convergence in the metric L of trigonometric interpolation sine polinomials of functions with monotone and quasimonotone Fourier coefficients is considered.     

On the zeros on the critical line of L-functions corresponding to automorphic cusp forms

We consider an automorphic cusp form of integer weight k ≥ 1, which is the eigenfunction of all Hecke operators. It is proved that, for the L-series whose coefficients correspond to the Fourier coefficients of such an automorphic form, the positive fraction of nontrivial zeros lie on the critical line.