A Hybrid Approach to Spectral Reconstruction of Piecewise Smooth Functions

Consider a piecewise smooth function for which the (pseudo-)spectral coefficients are given. It is well known that while spectral partial sums yield exponentially convergent approximations for smooth functions, the results for piecewise smooth functions are poor, with spurious oscillations developing near the discontinuities and a much reduced overall convergence rate. This behavior, known as the Gibbs phenomenon, is considered as one of the major drawbacks in the application of spectral methods. Various types of reconstruction methods developed for the recovery of piecewise smooth functions have met with varying degrees of success. The Gegenbauer reconstruction method, originally proposed by Gottlieb et al. has the particularly impressive ability to reconstruct piecewise analytic functions with exponential convergence up to the points of discontinuity. However, it has been sharply criticized for its high cost and susceptibility to round-off error. In this paper, a new approach to Gegenbauer reconstruction is considered, resulting in a reconstruction method that is less computationally intensive and costly, yet still enjoys superior convergence. The idea is to create a procedure that combines the well known exponential filtering method in smooth regions away from the discontinuities with the Gegenbauer reconstruction method in regions close to the discontinuities. This hybrid approach benefits from both the simplicity of exponential filtering and the high resolution properties of the Gegenbauer reconstruction method. Additionally, a new way of computing the Gegenbauer coefficients from Jacobian polynomial expansions is introduced that is both more cost effective and less prone to round-off errors.     

A practical assessment of spectral accuracy for hyperbolic problems with discontinuities

Numerical experiments are performed to compare the accuracy obtained when physical and transform space filters are used to smooth the oscillations in Fourier collocation approximations to discontinuous solutions of a linear wave equation. High-order accuracy can be obtained away from a discontinuity but the order is strongly filter dependent. Polynomial order accuracy is demonstrated when smooth high-order Fourier filters are used. Spectral accuracy is obtained with the physical space filter of Gottlieb and Tadmor.     

Fourier Spectral Methods for Degasperis–Procesi Equation with Discontinuous Solutions

In this paper, we develop, analyze and test the Fourier spectral methods for solving the Degasperis–Procesi (DP) equation which contains nonlinear high order derivatives, and possibly discontinuous or sharp transition solutions. The \(L^2\) stability is obtained for general numerical solutions of the Fourier Galerkin method and Fourier collocation (pseudospectral) method. By applying the Gegenbauer reconstruction technique as a post-processing method to the Fourier spectral solution, we reduce the oscillations arising from the discontinuity successfully. The numerical simulation results for different types of solutions of the nonlinear DP equation are provided to illustrate the accuracy and capability of the methods.     

Revisiting Branch and Bound Search Strategies for Machine Scheduling Problems

In the design of exact methods for NP-hard machine scheduling problems, branch and bound algorithms have always been widely considered. In this work we revisit the classic search strategies for branch and bound schemes. We consider a systematic application of the well known dynamic programming dominance property for machine scheduling problems. Several conditions concerning the application of the proposed property with respect to best first, depth first, breadth first search strategies and problem characteristics are presented. Computational testing on single machine and flow shop problems validate in practice the efficiency of the considered approach and suggest that the traditional choice of depth first search with respect to best first and breadth first is strongly questionable.     

A Fast Spectral Subtractional Solver for Elliptic Equations

The paper presents a fast subtractional spectral algorithm for the solution of the Poisson equation and the Helmholtz equation which does not require an extension of the original domain. It takes O(N ² log N) operations, where N is the number of collocation points in each direction. The method is based on the eigenfunction expansion of the right hand side with integration and the successive solution of the corresponding homogeneous equation using Modified Fourier Method. Both the right hand side and the boundary conditions are not assumed to have any periodicity properties. This algorithm is used as a preconditioner for the iterative solution of elliptic equations with non-constant coefficients. The procedure enjoys the following properties: fast convergence and high accuracy even when the computation employs a small number of collocation points. We also apply the basic solver to the solution of the Poisson equation in complex geometries.     

A series solution algorithm for initial boundary-value problems with variable properties

A multiple infinite trigonometric cum polynomial series method for solving initial-boundary value problems governed by hyperbolic differential equations with variable coefficients is developed. The method proposed herein can be easily applied to a broad class of engineering systems including those cases where boundary conditions may vary with time. In the proposed mathematical technique, the solution form is assumed as a combination of infinite Fourier series and polynomial series of nth order, where n is the order of the differential equation. The coefficients of the polynomial series are obtained as functions of undetermined Fourier series coefficients by satisfying the initial-boundary conditions. The variable coefficients are expanded in appropriate half-range sine or cosine series. Insertion of the above Fourier-polynomial series solutions into the differential equation and application of orthogonality conditions leads to a linear summation equation which can be solved in open form. However, the authors have developed a closed-form series solution consisting of a highly efficient algorithm. The major advantage of this technique is the development of a solution algorithm, coupled with the multiple infinite trigonometric cum polynomial series solutions, leading to fast converging series solutions. A representative initial and boundary value problem governed by hyperbolic partial differential equations of variable coefficients is presented herein to demonstrate the efficiency and accuracy of the method.     

Family of spectral filters for discontinuous problems

It is well known that spectral approximations of hyperbolic time-dependent equations can lead to incoherent results in the case where the solution is discontinuous. However, it has been proved that the spectral coefficients of the approximation are computed precisely. In this article we present and analyze a class of filters that allows the recovering of the solution with an exponential accuracy.     

Spectral Estimation by AFT Computation

Di Lecce, V., and Guerriero, A., Spectral Estimation by AFT Computation,Digital Signal Processing6(1996) 213–223.At the beginning of this century Bruns developed a method for computing the coefficients of the Fourier series of a periodic functiony(t) using the Möbius inversion formula. This idea for Fourier analysis was considered again by Wintner from an arithmetical point of view in 1945. In recent papers, many authors have shown that the arithmetic Fourier transform (AFT) computation is more convenient in signal processing, requiring a reduced computation load, than are fast Fourier transform and convolution algorithms. The data dependence in the AFT is not uniform (this algorithm requires nonequidistant inputs to produce equidistant spectral coefficients). To have a series of suitable values as AFT inputs, oversampling or interpolation is used. In these papers, bases on algorithms, evaluations of errors in the spectral coefficients computation using AFT, and the complexity of different hardware and software solutions for the AFT computation are proposed. The spectral coefficients computed via AFT and via discrete Fourier transform are compared in terms of accuracy. AFT computation proves to be an easy task but its software or hardware implementation is much more complex. Furthermore there is not a complete evaluation of AFT in any of the papers. Our aim is to provide a complete evaluation of this algorithm.     

Fast Tensor-Product Solvers: Partially Deformed Three-dimensional Domains

We discuss the numerical solution of partial differential equations in a particular class of three-dimensional geometries; the two-dimensional cross section (in the xy-plane) can have a general shape, but is assumed to be invariant with respect to the third direction. Earlier work has exploited such geometries by approximating the solution as a truncated Fourier series in the z-direction. In this paper we propose a new solution algorithm which also exploits the tensor-product feature between the xy-plane and the z-direction. However, the new algorithm is not limited to periodic boundary conditions, but works for general Dirichlet and Neumann type of boundary conditions. The proposed algorithm also works for problems with variable coefficients as long as these can be expressed as a separable function with respect to the variation in the xy-plane and the variation in the z-direction. For problems where the new method is applicable, the computational cost is very competitive with the best iterative solvers. The new algorithm is easy to implement, and useful, both in a serial and parallel context. Numerical results demonstrating the superiority of the method are presented for three-dimensional Poisson and Helmholtz problems using both low order finite elements and high order spectral element discretizations.     

Optimality of Euler-type algorithms for approximation of stochastic differential equations with discontinuous coefficients

We consider the pointwise approximation of solutions of scalar stochastic differential equations with discontinuous coefficients. We assume the singularities of coefficients to be unknown. We show that any algorithm which does not locate the discontinuities of a diffusion coefficient has the error at least Ω(n^{?min{1/2, ?}}), where ?∈(0, 1] is the Hölder exponent of the coefficient. In order to obtain better results, we consider algorithms that adaptively locate the unknown singularities. In the additive noise case, for a single discontinuity of a diffusion coefficient, we define an Euler-type algorithm based on adaptive mesh which obtains an error of order n^??. That is, this algorithm preserves the optimal error known from the Hölder continuous case. In the case of multiple discontinuities we show, both for the additive and the multiplicative noise case, that the optimal error is Θ(n^{?min{1/2, ?}}), even for the algorithms locating unknown singularities.     

The computation of complete and reduced sets of orthogonal spectral coefficients for logic design and pattern recognition purposes

The classic methods of computing the spectral coefficient values for any n-variable binary function, involving a 2ⁿ × 2ⁿ transform matrix, are reviewed. From this established starting point methods of generating the full set of spectral coefficients from decompositions of the function are considered, followed by possible methods of generating a reduced set of coefficients which may be sufficient for certain practical applications.     

A Note on the Spectral Collocation Approximation of Some Differential Equations with Singular Source Terms

The solution of differential equations with singular source terms contains the local jump discontinuity in general and its spectral approximation is oscillatory due to the Gibbs phenomenon. To minimize the Gibbs oscillations near the local jump discontinuity and improve convergence, the regularization of the approximation is needed. In this note, a simple derivative of the discrete Heaviside function H _c (x) on the collocation points is used for the approximation of singular source terms δ(x−c) or δ ⁽ⁿ⁾(x−c) without any regularization. The direct projection of H _c (x) yields highly oscillatory approximations of δ(x−c) and δ ⁽ⁿ⁾(x−c). In this note, however, it is shown that the direct projection approach can yield a non-oscillatory approximation of the solution and the error can also decay uniformly for certain types of differential equations. For some differential equations, spectral accuracy is also recovered. This method is limited to certain types of equations but can be applied when the given equation has some nice properties. Numerical examples for elliptic and hyperbolic equations are provided. The current address: Department of Mathematics, State University of New York at Buffalo, Buffalo, NY 14260-2900, USA.     

Modeling of first-order photobleaching kinetics using Krylov subspace spectral methods

We solve the first order 2-D reaction–diffusion equations which describe binding-diffusion kinetics using the photobleaching scanning profile of a confocal laser scanning microscope, approximated by a Gaussian laser profile. We show how to solve the first-order photobleaching kinetics partial differential equations (PDEs) using a time-stepping method known as a Krylov subspace spectral (KSS) method. KSS methods are explicit methods for solving time-dependent variable-coefficient partial differential equations. They approximate Fourier coefficients of the solution using Gaussian quadrature rules in the spectral domain. In this paper, we show how a KSS method can be used to obtain not only an approximate numerical solution, but also an approximate analytical solution when using initial conditions that come from pre-bleach steady states and also general initial conditions, to facilitate asymptotic analysis. Analytical and numerical results are presented. It is observed that although KSS methods are explicit, it is possible to use a time step that is far greater than what the CFL condition would indicate.     

Ehlers pan-sharpening performance enhancement using HCS transform for n-band data sets

The Ehlers fusion method, which combines a standard intensity-hue-saturation (IHS) transform with fast Fourier transform filtering, is a high spectral characteristics preservation algorithm for multitemporal and multisensor data sets. However, for data sets of more than three bands, the fusion process is complicated, because only every three bands are fused repeatedly for multiple times until all bands are fused. The hyper-spherical colour sharpening (HCS) fusion method can fuse a data set with an arbitrary number of bands. The HCS approach uses a transform between an n-dimensional Cartesian space and an n-dimensional hyper-spherical space to get one single intensity component and n ? 1 angles. Moreover, from a structural point of view, the hyper-spherical colour space is very similar to the IHS colour space. Hence, we propose to combine the Ehlers fusion with an HCS transform to fuse n-band data sets with high spectral information preservation, even hyper-spectral images. A WorldView-2 data set including a panchromatic and eight multispectral bands is used for demonstrating the effectiveness and quality of the new Ehlers –HCS fusion. The WorldView-2 image covers different landscapes such as agriculture, forest, water and urban areas. The fused images are visually and quantitatively analysed for spectral preservation and spatial improvement. Pros and cons of the applied fusion methods are related to the analysed different landscapes. Overall, the Ehlers –HCS method shows the efficacy for n-band fusion.     

Compact Representation of Spectral BRDFs Using Fourier Transform and Spherical Harmonic Expansion

This paper proposes a compact method to represent isotropic spectral BRDFs. In the first step, we perform a Fourier transform in the wavelength dimension. The resulting Fourier coefficients of the same order depend on three angles: the polar angle of the incident light, and the polar and azimuth angles of the outgoing light. In the second step, given an incident light angle, when the Fourier coefficients of the same order have an insensitive dependency on the outgoing direction, we represent these Fourier coefficients using a linear combination of spherical harmonics. Otherwise, we first decompose these Fourier coefficients into a smooth background that corresponds to diffuse component and a sharp lobe that corresponds to specular component. The smooth background is represented using a linear combination of spherical harmonics, and the sharp lobe using a Gaussian function. The representation errors are evaluated using spectral BRDFs obtained from measurement or generated from the Phong model. While maintaining sufficient accuracy, the proposed representation method has achieved data compression over a hundred of times. Examples of spectral rendering using the proposed method are also shown.     

Block Toeplitz matrices and preconditioning

We study the asymptotic behaviour of the eigenvalues of Hermitiann×n block Topelitz matricesT _n , withk×k blocks, asn tends to infinity. No hypothesis is made concerning the structure of the blocks. Such matrices{T _n } are generated by the Fourier coefficients of a Hermitian matrix valued functionf∈L ², and we study the distribution of their eigenvalues for largen, relating their behaviour to some properties of the functionf. We also study the eigenvalues of the preconditioned matrices{P _n ⁻¹ T_n}, where the sequence{P _n } is generated by a positive definite matrix valued functionp. We show that the spectrum of anyP _n ⁻¹ T _n is contained in the interval [r, R], wherer is the smallest andR the largest eigenvalue ofp ⁻¹ f. We also prove that the firstm eigenvalues ofP _n ⁻¹ T_n tend tor and the lastm tend toR, for anym fixed. Finally, exact limit values for both the condition number and the conjugate gradient convergence factor for the preconditioned matricesP _n ⁻¹ T_n are computed.     

A note on a system theoretic approach to a conjecture by Peller-Khrushchev

Based on the construction of infinite dimensional balanced realizations an alternative solution to the following inverse spectral problem is presented: Given a monotonically decreasing sequence of positive numbers (σ_n)_{n 1}, does there exist a Hankel operator whose sequence of singular values is (σ_n)_{n 1}?     

Fault detection for singular switched linear systems with multiple time-varying delay in finite frequency domain

This paper deals with the problem of the fault detection (FD) for continuous-time singular switched linear systems with multiple time-varying delay. In this paper, the actuator fault is considered. Besides, the systems faults and unknown disturbances are assumed in known frequency domains. Some finite frequency performance indices are initially introduced to design the switched FD filters which ensure that the filtering augmented systems under switching signal with average dwell time are exponentially admissible and guarantee the fault input sensitivity and disturbance robustness. By developing generalised Kalman–Yakubovic–Popov lemma and using Parseval's theorem and Fourier transform, finite frequency delay-dependent sufficient conditions for the existence of such a filter which can guarantee the finite-frequency H_? and H_∞ performance are derived and formulated in terms of linear matrix inequalities. Four examples are provided to illustrate the effectiveness of the proposed finite frequency method.     

A probabilistic approach to multivariable robust filtering andopen-loop control

A new approach to robust filtering, prediction, and smoothing of discrete-time signal vectors is presented. Linear time-invariant filters are designed to be insensitive to spectral uncertainty in signal models. The goal is to obtain a simple design method, leading to filters which are not overly conservative. Modeling errors are described by sets of models, parameterized by random variables with known covariances. These covariances could either be estimated from data or be used as robustness “tuning knobs.” A robust design is obtained by minimizing the ℋ₂-norm or, equivalently, the mean square estimation error, averaged with respect to the assumed model errors. A polynomial solution, based on an averaged spectral factorization and a unilateral Diophantine equation, is derived. The robust estimator is referred to as a cautious Wiener filter. It turns out to be only slightly more complicated to design than an ordinary Wiener filter. The methodology can be applied to any open-loop filtering or control problem. In particular, we illustrate this for the design of robust multivariable feedforward regulators, decoupling and model matching filters     

A Hybrid Fourier–Chebyshev Method for Partial Differential Equations

We propose a pseudospectral hybrid algorithm to approximate the solution of partial differential equations (PDEs) with non-periodic boundary conditions. Most of the approximations are computed using Fourier expansions that can be efficiently obtained by fast Fourier transforms. To avoid the Gibbs phenomenon, super-Gaussian window functions are used in physical space. Near the boundaries, we use local polynomial approximations to correct the solution. We analyze the accuracy and eigenvalue stability of the method for several PDEs. The method compares favorably to traditional spectral methods, and numerical results indicate that for hyperbolic problems a time step restriction of O(1/N) is sufficient for stability. R.B. Platte’s address after December 2009: Arizona State University, Department of Mathematics and Statistics, Tempe, AZ, 85287-1804.