Search

Based on the splitting form of the Green's function, a hybrid fast algorithm is proposed for efficient analysis of multiscale problems. In this algorithm, the Green's function is a priori split into two parts: a spectrally band-limited part and a spatially localized part. Then, the fast Fourier transforms (FFT) utilizing the global Cartesian grid and the matrix compression method aided by an adaptive octree grouping are implemented for these two parts, respectively. Compared with the traditional methods which only employ the FFT for acceleration, the proposed hybrid fast algorithm is capable of maintaining low memory consumption in multiscale problems without compromising time cost. Moreover, the proposed algorithm does not need cumbersome geometric treatment to implement the hybridization, and can be established in a concise and straightforward manner. Several numerical examples discretized with multiscale meshes are provided to demonstrate the computational performance of proposed hybrid fast algorithm. [ABSTRACT FROM AUTHOR]

This article deals with efficient vectorization of the fast Fourier transform algorithm while focusing on Cooley–Tukey versions with power-of-two radixes. Aside from examples of optimizations for 256 and 512-bit vectors, this work also discusses relations between individual radix-based versions, vectorization and OpenMP threading. Ideas are progressing into a timeless design of the FFT algorithm, which can work with any vector size and radix version through conversion into radix-2 output permutation. Furthermore, the implementation of the Cache Optimized Bit-Reversal algorithm, which doubles the performance of its predecessor, is introduced. [ABSTRACT FROM AUTHOR]

Purpose: Most commercially available treatment planning systems (TPSs) approximate the continuous delivery of volumetric modulated arc therapy (VMAT) plans with a series of discretized static beams for treatment planning, which can make VMAT dose computation extremely inefficient. In this study, we developed a polar‐coordinate‐based pencil beam (PB) algorithm for efficient VMAT dose computation with high‐resolution gantry angle sampling that can improve the computational efficiency and reduce the dose discrepancy due to the angular under‐sampling effect. Methods and Materials: 6 MV 1×1mm2$1 \times 1{\rm{\;m}}{{\rm{m}}^2}$ pencil beams were simulated on a uniform cylindrical phantom under an EGSnrc Monte Carlo (MC) environment. The MC‐generated PB kernels were collected in the polar coordinate system for each bixel on a 40×40cm2$40 \times 40{\rm{\;c}}{{\rm{m}}^2}$ fluence map and subsequently fitted via a series of Gaussians. The fluence was calculated using a detectors' eye view with off‐axis and MLC transmission factors corrected. Doses of VMAT arc on the phantom were computed by summing the convolution results between the corresponding PB kernels and fluence for each bixel in the polar coordinate system. The convolution was performed using fast Fourier transform to expedite the computing speed. The calculated doses were converted to the Cartesian coordinate system and compared with the reference dose computed by a collapsed cone convolution (CCC) algorithm of the TPS. A heterogeneous phantom was created to study the heterogeneity corrections using the proposed algorithm. Ten VMAT arcs were included to evaluate the algorithm performance. Gamma analysis and computation complexity theory were used to measure the dosimetric accuracy and computational efficiency, respectively. Results: The dosimetric comparisons on the homogeneous phantom between the proposed PB algorithm and the CCC algorithm for 10 VMAT arcs demonstrate that the proposed algorithm can achieve a dosimetric accuracy comparable to that of the CCC algorithm with average gamma passing rates of 96% (2%/2mm) and 98% (3%/3mm). In addition, the proposed algorithm can provide better computational efficiency for VMAT dose computation using a PC equipped with a 4‐core processor, compared to the CCC algorithm utilizing a dual 10‐core server. Moreover, the computation complexity theory reveals that the proposed algorithm has a great advantage with regard to computational efficiency for VMAT dose computation on homogeneous medium, especially when a fine angular sampling rate is applied. This can support a reduction in dose errors from the angular under‐sampling effect by using a finer angular sampling rate, while still preserving a practical computing speed. For dose calculation on the heterogeneous phantom, the proposed algorithm with heterogeneity corrections can still offer a reasonable dosimetric accuracy with comparable computational efficiency to that of the CCC algorithm. Conclusions: We proposed a novel polar‐coordinate‐based pencil beam algorithm for VMAT dose computation that enables a better computational efficiency while maintaining clinically acceptable dosimetric accuracy and reducing dose error caused by the angular under‐sampling effect. It also provides a flexible VMAT dose computation structure that allows adjustable sampling rates and direct dose computation in regions of interest, which makes the algorithm potentially useful for clinical applications such as independent dose verification for VMAT patient‐specific QA. [ABSTRACT FROM AUTHOR]

This paper presents a methodology to study non-twist invariant circles and their bifurcations for area preserving maps, which is supported on the theoretical framework developed in Gonzalez-Enriquez et al. (Mem. Amer. Math. Soc. 227:vi+115, 2014). We recall that non-twist invariant circles are characterized not only by being invariant, but also by having some specified normal behavior. The normal behavior may endow them with extra stability properties (e.g., against external noise), and hence, they appear as design goals in some applications, e.g., in plasma physics, astrodynamics and oceanography. The methodology leads to efficient algorithms to compute and continue, with respect to parameters, non-twist invariant circles. The algorithms are quadratically convergent and, when implemented using FFT, have low storage requirement and low operations count per step. Furthermore, the algorithms are backed up by rigorous a posteriori theorems, proved and discussed in detail in Gonzalez-Enriquez et al. (Mem. Amer. Math. Soc. 227:vi+115, 2014), which give sufficient conditions guaranteeing the existence of a true non-twist invariant circle, provided an approximate invariant circle is known. Hence, one can compute confidently even very close to breakdown. With some extra effort, the calculations could be turned into computer-assisted proofs, see Figueras et al. (Found. Comput. Math. 17:1123–1193, 2017) for examples of the latter. The algorithms are also guaranteed to converge up to the breakdown of the invariant circles, and then, they are suitable to compute regions of parameters where the non-twist invariant circles exist. The calculations involved in the computation of the boundary of these regions are very robust, and they do not require symmetries and can run without continuous manual adjustments, largely improving methods based on the computation of very long period periodic orbits to approximate invariant circles. This paper contains a detailed description of our algorithms, the corresponding implementation and some numerical results, obtained by running the computer programs. In particular, we include calculations for two-dimensional parameter regions where non-twist invariant circles (with a prescribed frequency) exist. Indeed, we present systematic results in systems that do not contain symmetry lines, which seem to be unaccessible for previous methods. These numerical explorations lead to some open questions, also included here. [ABSTRACT FROM AUTHOR]

A new algorithm for stable solution of a three-dimensional scalar inverse problem of acoustic sensing of an inhomogeneous medium in a cylindrical domain is proposed. Data for its solution is the complex amplitude of the wave field measured outside the acoustic inhomogeneities in the cylindrical layer. With the help of the Fourier transform and Fourier series, the inverse problem is reduced to a set of one-dimensional Fredholm integral equations of the first kind. Next, the complex amplitude of the wave field is computed in the inhomogeneity region and the desired sonic velocity field is found in this region. When run on a moderate-performance personal computer, the algorithm takes tens of seconds to solve the inverse problem on rather fine three-dimensional grids. The accuracy of the algorithm is analyzed numerically as applied to test inverse problems at different frequencies, and the stability of the algorithm with respect to data perturbations is investigated. [ABSTRACT FROM AUTHOR]

A novel higher-order probe correction algorithm is introduced for the spherical near field antenna measurements. The measured signal is processed by the fast Fourier transform along ϕ direction and integrated numerically along θ direction, thus converting the transmission formula into a series of small matrix equations. In a virtual example simulated using FEKO, a Yagi antenna is used as a higher-order probe to measure a Taylor array. It is shown that the proposed method is faster, more accurate and more stable than the FFT/matrix inverse method. Furthermore, the number of sampling points of the former is only half of that of the latter. [ABSTRACT FROM AUTHOR]

Optoacoustic signals are typically reconstructed into images using inversion algorithms applied in the time-domain. However, time-domain reconstructions can be computationally intensive and therefore slow when large amounts of raw data are collected from an optoacoustic scan. Here we considered a fast weighted ${\omega }-{k}$ (FWOK) algorithm operating in the frequency domain to accelerate the inversion in raster-scan optoacoustic mesoscopy (RSOM), while seamlessly incorporating impulse response correction with minimum computational burden. We investigated the FWOK performance with RSOM measurements from phantoms and mice in vivo and obtained 360-fold speed improvement over inversions based on the back-projection algorithm in the time-domain. This previously unexplored inversion of in vivo optoacoustic data with impulse response correction in frequency domain reconstructions points to a promising strategy of accelerating optoacoustic imaging computations, toward video-rate tomography. [ABSTRACT FROM AUTHOR]

This paper presents an efficient implementation of the inversion algorithm based on the conjugate-gradient method (CGM) for solving inverse scattering problems. The original CGM provides good image reconstruction and robustness to noise-corrupted data. This method requires the solution of the forward scattering problem and the Fréchet derivative operator of the cost function at each iteration step. However, these procedures can make the computational cost prohibitive, even for moderately sized problems. To avoid the computational burden, a two-step conjugate gradient fast Fourier transform (CG-FFT) procedure is proposed. Such an approach reduces the computational cost and storage requirements of the CGM implementation. The efficient CGM is found to share a computational complexity similar to the distorted-Born iterative method (DBIM). Thus the convergence speed and accuracy of the CGM is compared with the DBIM. Numerical tests using both synthetic and experimental data show effectiveness for solving 2D inverse scattering problems. [ABSTRACT FROM AUTHOR]

Mass of an object is an important characteristic for quality assessment. However, in some cases, it is hard to measure the mass of objects with instruments directly. In this paper, we proposed a novel method based on Fuzzy c-means (FCM) to measure the mass of an object by analyzing the deformation degree in a grid pattern. In the spatial field, thin plate spline (TPS) algorithm was adopted to calculate the minimum deformation bending energy in order to give a quantitative analysis of the weight; In frequency domain, the Fast Fourier Transform (FFT) algorithm was used to calculate the spectrum within a deformation frequency area before and after the change of grids, from which the relationship between weight and spectrum was investigated using FCM algorithm. Two different equations evaluated by the above two methods were proposed in order to calculate the mass of an object. Both of them showed a high level of explanatory power of R2 (R2 = 0.9833 and R2 = 0.9698, respectively). The equations were then used to determine the estimated mass. Estimated and measured values were plotted against each other. A high correlation (R2 = 0.9833 and R2 = 0.9698, respectively) was found between actual and calculated mass. Finally, Bland-Altman plot was introduced to access the agreement of the calculated mass and the actual mass. The average bias was –54.408 g and –0.007 g for spatial domain method and frequency domain method, respectively. Theoretical analysis and experiments were performed to verify the effectiveness of our approaches. [ABSTRACT FROM AUTHOR]

This paper proposes method of series direct current (DC) arc fault protection using low cost microcontroller. Series DC arc fault occurs when gap between conductor or wire flows a current. Series DC arc fault can cause fire hazard if do not detected and protected. However, Series DC arc fault is difficult to detected using conventional protection. To detect series DC arc fault accurately using fast Fourier transform (FFT). FFT is used to transform signal in time domain to frequency domain. Series DC arc fault has different characteristic compared by normal current in frequency domain. Therefore, the proposed algorithm for protection of series DC arc fault based on magnitudes of the current in frequency domain. Hardware system is implemented by 100 V DC power supply and DC arc fault generator. Test result is conducted experimentally under varying of load current such as 2 A, 2.5 A, 3 A, 3.5 A, 4 A and 5 A. Experimental testing results show that Series DC arc fault protection has time for trip of 0.48 s, 0.26 s, 1.04 s, 0.68 s, 0.44 s and 0.48, respectively. The fastest time for trip is 0.26 s with current of 2.5 A. Therefore, the proposed algorithm for series DC arc fault protection can operate to trip accurately and have the good performance. [ABSTRACT FROM AUTHOR]

The proliferation of renewable-based distributed generators poses protection challenges for the overcurrent relays due to the intermittent nature and control schemes. Converters present in the AC side restrict the fault current up to two per unit. Therefore, the overcurrent relay present in the AC microgrid maloperates during the fault. The proposed technique is based on the corresponding sum of the current samples obtained after every half-cycle (Ts/2), computed for each phase, and utilized to derive an index to detect the fault. The index thus derived is robust to noises, load variations, and other transients in the system. However, the technique requires removing transients and other noises before comparing the threshold for fault detection, which is resolved using the fast Fourier transform (FFT). Further, the magnitude of decaying DC (as another index) present in the signal is calculated using the least square technique for detecting the three-phase fault. The proposed algorithm is tested on an IEEE 14-bus system and a Real-Time Digital Simulator microgrid model. The fault detection technique is accurate for different faults under different operating conditions like noise, CT saturation, sudden load change, etc. [ABSTRACT FROM AUTHOR]

Mass of an object is an important characteristic for quality assessment. However, in some cases, it is hard to measure the mass of objects with instruments directly. In this paper, we proposed a novel method based on Fuzzy c-means (FCM) to measure the mass of an object by analyzing the deformation degree in a grid pattern. In the spatial field, thin plate spline (TPS) algorithm was adopted to calculate the minimum deformation bending energy in order to give a quantitative analysis of the weight; In frequency domain, the Fast Fourier Transform (FFT) algorithm was used to calculate the spectrum within a deformation frequency area before and after the change of grids, from which the relationship between weight and spectrum was investigated using FCM algorithm. Two different equations evaluated by the above two methods were proposed in order to calculate the mass of an object. Both of them showed a high level of explanatory power of R2 (R2 = 0.9833 and R2 = 0.9698, respectively). The equations were then used to determine the estimated mass. Estimated and measured values were plotted against each other. A high correlation (R2 = 0.9833 and R2 = 0.9698, respectively) was found between actual and calculated mass. Finally, Bland-Altman plot was introduced to access the agreement of the calculated mass and the actual mass. The average bias was –54.408 g and –0.007 g for spatial domain method and frequency domain method, respectively. Theoretical analysis and experiments were performed to verify the effectiveness of our approaches. [ABSTRACT FROM AUTHOR]

We use the well-known observation that the solutions of Jacobi's differential equation can be represented via the non-oscillatory phase and amplitude functions to develop a fast algorithm for computing multi-dimensional Jacobi polynomial transforms. More explicitly, it follows from this observation that the matrix corresponding to the discrete Jacobi transform is the Hadamard product of a numerically low-rank matrix and a multi-dimensional discrete Fourier transform (DFT) matrix. The application of the Hadamard product can be carried out via r d fast Fourier transforms (FFTs), where r = O (log ⁡ n log ⁡ log ⁡ n) and d is the dimension, resulting in a nearly optimal algorithm to compute the multidimensional Jacobi polynomial transform. [ABSTRACT FROM AUTHOR]

In this article, an improved fast Fourier transform (FFT)–based millimeter-wave imaging algorithm with range compensation is presented, which can be used to reconstruct 3D images for near-field multiple-input multiple-output synthetic aperture radar (MIMO-SAR). The frequency-domain interpolation is avoided and only one-step spherical-wave decomposition is employed in this algorithm. During the image reconstruction process, the amplitude factor is considered for the compensation of signal propagation loss, and the final target image can be obtained by FFT/IFFT and coherent accumulation steps. As demonstrated with numerical theoretical analysis and experimental results, the proposed method greatly reduces the computational load but ensures the quality of image reconstruction compared to the back-projection (BP) algorithm. Moreover, it is superior to the MIMO-range migration algorithm (MIMO-RMA) in compensating propagation loss and other performance indexes in the image reconstruction results. [ABSTRACT FROM AUTHOR]

This work describes a new scheme for denoising noisy electrocardiogram (ECG) signals. In the first step, the noise variance is estimated using the well-known DONOHO's estimator followed by the wavelet-based baseline wander removing. In the second step, the estimated variance is employed in the adaptive 1D Wiener filter to reduce the additive noise. Next, a Low Pass filter, based on the FFT, is applied on the resulting denoised signal. Furthermore, a cascaded Savitzky–Golay (SG) smoother filter is applied to refine the restoration process. The final step consists in the recovering of the R -peaks and the surrounding areas. It can be reported that the suggested algorithm is optimal for the additive Gaussian noise and is useful for other types of noises. Both qualitative and quantitative results, achieved from several experimental tests, establish high-quality restoration ability and the efficiency of the proposed method. Thus, when compared to some powerful techniques recently published, the designed algorithm demonstrates very competitive performances. [ABSTRACT FROM AUTHOR]

In the sparse polynomial multiplication problem, one is asked to multiply two sparse polynomials $f$ and $g$ in time that is proportional to the size of the input plus the size of the output. The polynomials are given via lists, $F$ and $G$ , of their coefficients. Cole and Hariharan (STOC 02) have given a nearly optimal algorithm when the coefficients are positive, and Arnold and Roche (ISSAC 15) devised an algorithm running in time proportional to the “structural sparsity” of the product, i.e. the set $\mathrm {supp}(F) + \mathrm {supp}(G)$. The latter algorithm is particularly efficient when there are not “too many cancellations” of coefficients in the product. In this work we give a clean, nearly optimal algorithm for the sparse polynomial multiplication problem. [ABSTRACT FROM AUTHOR]

In ultra-high sampling rates, FFT is widely used for acoustic emission signals. In this manuscript, the effectual architecture of hardware is presented based on the execution of FFT due to radix-2 frequency decimation algorithm (R2DIF) and channeled method that allows data to be effectively shared through storage by shift registers. An optimal rotation method/design uses the modified digital coordinate rotation computer algorithm (m-CORDIC) as well as Radix- 2r depending on coding scheme to replace complex multiplier as FFT. The m-CORDIC algorithm enhances computing confluence, while Radix-2r allows the logarithmic reduction of the adder steps. The suggested design does not need large blocks of memory used to maintain the factor as twiddle. Experimental outcomes displays the presented design performs the existing methods by achieving high accuracy and throughput. Compared to the CSD as well as DBNS, novel radix-2r encoding desires an average of 23.12% and 3.07% fewer additions, respectively. The expansion of CSD is canonical signed-digit. [ABSTRACT FROM AUTHOR]

The Iterative Filtering method is a technique developed recently for the decomposition and analysis of nonstationary and nonlinear signals. In this work, we propose two alternative formulations of the original algorithm which allows to transform the iterative filtering method into a direct technique, making the algorithm closer to an online algorithm. We present a few numerical examples to show the effectiveness of the proposed approaches. [ABSTRACT FROM AUTHOR]

The fast Fourier transform-moving average (FFT-MA) is an efficient method for the generation of geostatistical simulations. The method relies on the calculation of a filter operator based on the covariance function of interest and the convolution of the filter with a white noise, to generate multiple realizations of spatially correlated variables. In this work, a revisited mathematical formulation of the FFT-MA method, with the exact expression of the filter, is presented. The proposed derivation of the filter is based on the Wiener–Khinchin theorem and the application of the Fourier transform in a discrete domain. In the specific case of white noise, the proposed formulation leads to the same expression of the traditional algorithm. However, the method can be applied to other types of noise. The proposed technique allows the calculation of a specific filter that imposes an exact covariance function on the noise. Therefore, the experimental covariance function is exactly equal to the theoretical one, which is not the case for many common simulation techniques due to the limited sample size. Applications of the FFT-MA method to synthetic and real data sets, including exact interpolation, hard data conditioning and correlated simulations from cross-correlated noises, are also presented. [ABSTRACT FROM AUTHOR]

In this paper, we are concerned with the numerical solutions of the coupled fractional Klein-Gordon-Schrödinger equation. The numerical schemes are constructed by combining the Crank-Nicolson/leap-frog difference methods for the temporal discretization and the Galerkin finite element methods for the spatial discretization. We give a detailed analysis of the conservation properties in the senses of discrete mass and energy. Then the numerical solutions are shown to be unconditionally bounded in L2 −norm, H α 2 − semi-norm and L ∞ − norm, respectively. Based on the well-known Brouwer fixed-point theorem and the mathematical induction, the unique solvability of the discrete solutions is proved. Moreover, the schemes are proved to be unconditionally convergent with the optimal order O τ 2 + h r + 1 , where τ is the temporal step, h is the spatial grid size, and r is the order of the selected finite element space. Furthermore, by using the proposed decoupling and iterative algorithms, several numerical examples are included to support theoretical results and show the effectiveness of the schemes. Finally, the fast Krylov subspace solver with suitable circulant preconditioner is designed to effectively solve the Toeplitz-like linear systems. In each iterative step, this method can effectively reduce the memory requirement of above each finite element scheme from O M 2 to O(M), and the computational complexity from O M 3 to O (M log M) , where M is the number of grid nodes. Numerical tests are carried out to show that this fast algorithm is more practical than the traditional backslash and LU factorization/Cholesky decomposition methods, in terms of memory requirement and computational cost. [ABSTRACT FROM AUTHOR]

For the problem of the traditional partial matched filter( PMF) combined with fa st Fourier transform( FFT) could not accurately capture the time-division multiplexed binary offset carrier ( TMBOC) modulated signal, this paper proposed a capture method based on all-phase spectrum correction. Firstly, it received signal with PMF for partial correlation operation, then used the all-phase fast Fourier transform ( apFFT) algorithm to compensate the Doppler effect. Finally, the power spectrum was corrected in combination with the all-phase spectrum correction technique. The experimental results show that, under the same conditions, the proposed scheme improves the detection probability by about 3 dB than the PMF-FFT windowing algorithm, and shortens effectively the acquisition ti me . This algorithm captures the TMBOC signal more accurately than the PMF-FFT windowing algorithm. [ABSTRACT FROM AUTHOR]

A new algorithm is proposed for solving a three-dimensional scalar inverse problem of acoustic sensing in an inhomogeneous medium with given complex wave field amplitudes measured outside the inhomogeneity region. In the case of data measured in a "plane layer," the inverse problem is reduced via the Fourier transform to a set of one-dimensional Fredholm integral equations of the first kind. Next, the complex amplitude of the wave field is computed in the inhomogeneity region and the desired sonic velocity field is found in this region. When run on a moderate-performance personal computer (without parallelization), the algorithm takes several minutes to solve the inverse problem on rather fine three-dimensional grids. The accuracy of the algorithm is studied numerically as applied to test inverse problems at one and several frequencies simultaneously, and the stability of the algorithm with respect to data perturbations is analyzed. [ABSTRACT FROM AUTHOR]

This paper introduces the notion of numerical basis for a numerical space and uses it to establish a relation between a fast algorithm for computing a discrete linear transform and the problem of expanding a given finite set of matrices as a linear combination of rank-1 matrices. It is shown that the number of multiplications of the algorithm is given by the number of rank-1 matrices in the expansion. Applying this approach, an algorithm for computing three components of the nine-point discrete Fourier transform (DFT) and an algorithm to compute the seven-point DFT with the least possible number of multiplications are shown. [ABSTRACT FROM AUTHOR]

Abstract The discrete prolate spheroidal sequences (DPSS's) provide an efficient representation for discrete signals that are perfectly timelimited and nearly bandlimited. Due to the high computational complexity of projecting onto the DPSS basis – also known as the Slepian basis – this representation is often overlooked in favor of the fast Fourier transform (FFT). We show that there exist fast constructions for computing approximate projections onto the leading Slepian basis elements. The complexity of the resulting algorithms is comparable to the FFT, and scales favorably as the quality of the desired approximation is increased. In the process of bounding the complexity of these algorithms, we also establish new nonasymptotic results on the eigenvalue distribution of discrete time–frequency localization operators. We then demonstrate how these algorithms allow us to efficiently compute the solution to certain least-squares problems that arise in signal processing. We also provide simulations comparing these fast, approximate Slepian methods to exact Slepian methods as well as the traditional FFT based methods. [ABSTRACT FROM AUTHOR]

We present a new algorithm for the 2D sliding window discrete Fourier transform. Our algorithm avoids repeating calculations in overlapping windows by storing them in a tree data-structure based on the ideas of the Cooley-Tukey fast Fourier transform. For an N0 × N1 array and n0 × n1 windows, our algorithm takes O(N0 N1 n0 n1) operations. We provide a C implementation of our algorithm for the Radix-2 case, compare ours to existing algorithms, and show how our algorithm easily extends to higher dimensions. [ABSTRACT FROM AUTHOR]

The vertical gradient is an essential tool in interpretation algorithms. It is also the primary enhancement technique to improve the resolution of measured gravity and magnetic field data, since it has higher sensitivity to changes in physical properties (density or susceptibility) of the subsurface structures than the measured field. If the field derivatives are not directly measured with the gradiometers, they can be calculated from the collected gravity or magnetic data using numerical methods such as those based on fast Fourier transform technique. The gradients behave similar to high-pass filters and enhance the short-wavelength anomalies which may be associated with either small-shallow sources or high-frequency noise content in data, and their numerical computation is susceptible to suffer from amplification of noise. This behaviour can adversely affect the stability of the derivatives in the presence of even a small level of the noise and consequently limit their application to interpretation methods. Adding a smoothing term to the conventional formulation of calculating the vertical gradient in Fourier domain can improve the stability of numerical differentiation of the field. In this paper, we propose a strategy in which the overall efficiency of the classical algorithm in Fourier domain is improved by incorporating two different smoothing filters. For smoothing term, a simple qualitative procedure based on the upward continuation of the field to a higher altitude is introduced to estimate the related parameters which are called regularization parameter and cut-off wavenumber in the corresponding filters. The efficiency of these new approaches is validated by computing the first- and second-order derivatives of noise-corrupted synthetic data sets and then comparing the results with the true ones. The filtered and unfiltered vertical gradients are incorporated into the extended Euler deconvolution to estimate the depth and structural index of a magnetic sphere, hence, quantitatively evaluating the methods. In the real case, the described algorithms are used to enhance a portion of aeromagnetic data acquired in Mackenzie Corridor, Northern Mainland, Canada. [ABSTRACT FROM AUTHOR]

In this article, a fast‐iterative method and a fast‐direct method is proposed for solving one‐dimensional and two‐dimensional tempered fractional diffusion equations with constant coefficients. The proposed iterative method is accelerated by circulant preconditioning which is shown to converge superlinearly while the proposed direct method is based on circulant and skew‐circulant representation for Toeplitz matrix inversion. In one‐dimensional case, the operation cost of the proposed methods are both shown to be O ( N log N ) with O ( N ) memory requirement in each time step, where N is the number of spatial nodes. With the alternating direction implicit method, it is proven that the proposed fast solution algorithms can be extended to handle two‐dimensional tempered fractional diffusion equations with O ( N 2 log N ) operation cost and O ( N 2 ) memory requirement in each time step, where the number of spatial nodes in x ‐direction and y ‐direction both equal to N . Numerical examples are provided to illustrate the effectiveness and efficiency of the proposed methods. [ABSTRACT FROM AUTHOR]

We describe a fast, simple and stable transform of Chebyshev expansion coefficients to Jacobi expansion coefficients, and its inverse based on the numerical evaluation of Jacobi expansions at the Chebyshev-Lobatto points. This is achieved via decomposition of Hahn's interior asymptotic formula into a small sum of diagonally scaled discrete sine and cosine transforms and the use of stable recurrence relations. It is known that the Clenshaw-Smith algorithm is not uniformly stable on the entire interval of orthogonality. Therefore, Reinsch's modification is extended for Jacobi polynomials and employed near the endpoints to improve numerical stability. [ABSTRACT FROM AUTHOR]

Cubic-spline interpolation (CSI) scheme is known to be designed to resample the discrete image data based on the least-square method in conjunction with the cubic convolution interpolation (CCI) function. It is superior in performance and can be used together with the discrete cosine transform (DCT)-based image or video codec to improve the coding performance for a variety of high compression ratios. In this paper, we firstly make some comments on the direct computation algorithm for CSI scheme developed by Lin et al. Moreover, a low-complexity direct computation algorithm for CSI scheme is developed to further improve the computational efficiency. The mathematical derivations and simulation results indicate that such simplified CSI scheme using the proposed low-complexity direct computation algorithm can achieve almost the same objective and subjective performance with much fewer arithmetic operations in comparison with the CSI scheme using the direct computation algorithm. [ABSTRACT FROM AUTHOR]

We proposed an efficient iterative thresholding method for multi-phase image segmentation. The algorithm is based on minimizing piecewise constant Mumford–Shah functional in which the contour length (or perimeter) is approximated by a non-local multi-phase energy. The minimization problem is solved by an iterative method. Each iteration consists of computing simple convolutions followed by a thresholding step. The algorithm is easy to implement and has the optimal complexity O ( N log ⁡ N ) per iteration. We also show that the iterative algorithm has the total energy decaying property. We present some numerical results to show the efficiency of our method. [ABSTRACT FROM AUTHOR]

Simulation of the devastating excitations such as the ground motion and transient extreme winds is an important task in the structural response analysis when it comes to the nonlinearity, system stochasticity, parametric excitations and so on. Although the classic spectral representation method (SRM) is widely used in the nonstationary process simulation, it suffers from lower efficiency due to the unavailability of use of fast Fourier transform (FFT). In this study, the classic SRM is extended to the nonstationary process with the time-varying coherence. Then, the FFT-aided and almost accurate simulation algorithm for the nonstationary process with the time-varying coherence is developed with the help of the proper orthogonal decomposition (POD) which is used to factorize the decomposed evolutionary spectra. Especially, the more efficient simulation for the nonstationary process with time-invariant coherence is also proposed, where the spectral matrix decomposition, use of POD and execution of FFT can be reduced significantly. Two examples including downburst and typhoon winds are employed to evaluate the accuracy and efficiency of the proposed method. Results show that the method has the good performance in terms of the efficiency and accuracy. [ABSTRACT FROM AUTHOR]

Adaptive Fourier decomposition (AFD) has been found to be among the most effective greedy algorithms. AFD shows an outstanding performance in signal analysis and system identification. As compensation of effectiveness, the computation complexity is great, that is especially due to maximal selections of the parameters. In this paper, we explore the discretization of the 1-D AFD integration via with discrete Fourier transform (DFT), incorporating fast Fourier transform (FFT). We show that the new algorithm, called FFT-AFD, reduces the computational complexity from O ( M N 2 ) to O ( M N log N ) , the latter being the same as FFT. Through experiments, we verify the effectiveness, accuracy, and robustness of the proposed algorithm. The proposed FFT-based algorithm for AFD lays a foundation for its practical applications. [ABSTRACT FROM AUTHOR]

An O(N(logN)²/log log N) algorithm for the computation of the discrete Legendre transform and its inverse is described. The algorithm combines a recently developed fast transform for converting between Legendre and Chebyshev coefficients with a Taylor series expansion for Chebyshev polynomials about equally spaced points in the frequency domain. Both components are based on the fast Fourier transform, and as an intermediate step we obtain an O(N logN) algorithm for evaluating a degree-(N - 1) Chebyshev expansion on an N-point Legendre grid. Numerical results are given to demonstrate performance and accuracy. [ABSTRACT FROM AUTHOR]

In this paper, a combined numerical and experimental method, called Extended Load Confluence Algorithm, is presented to accurately predict the dynamic response of non-periodic structures when little or no information about the applied loads is available. This approach, which falls into the category of Shape Sensing methods, inputs limited experimental information acquired from sensors to a mapping algorithm that predicts the response at unmeasured locations. The proposed algorithm consists of three major cores: an experimental core for data acquisition, a numerical core based on Finite Element Method for modeling the structure, and a mapping algorithm that improves the numerical model based on a modal approach in the frequency domain. The robustness and precision of the proposed algorithm are verified through numerical and experimental examples. The results of this paper demonstrate that without a precise knowledge of the loads acting on the structure, the dynamic behavior of the system can be predicted in an effective and precise manner after just a few iterations. [ABSTRACT FROM AUTHOR]

This paper describes the fastest quantum algorithm at this moment for the quantum Fourier transform (QFT) over symmetric groups. We provide a new FFT (classical) algorithm over symmetric groups and then transform it to a quantum algorithm. The complexity of our QFT algorithm is O ( n 3 log ⁡ n ) , faster than the existing O ( n 4 log ⁡ n ) QFT algorithm. In addition, we show that the algorithm can be performed in O ( n 3 ) if the use of threshold gates is allowed. [ABSTRACT FROM AUTHOR]

This research aims to make a comparison between the analytical and numerical methods of simulation of the Gaussian beam propagation in free space. This comparison brings evaluation of the accuracy and applicability limitations of the angular spectrum diffraction algorithm. In this approach, planar harmonic waves are assumed as basic components of a propagating wave, so the algorithm combines the angular spectrum technique and the 2D fast Fourier transformation procedures. It means a quite different approach than the well-established Huygens–Fresnel–Rayleigh–Sommerfeld one, based on spherical waves. The Gaussian beam is a rare case of the exact analytical 3D solution of a specific wave diffraction problem, in paraxial scalar approximation. Gaussian beam form has been chosen here as an evaluation reference. It allows to avoid comparisons between two numerical procedures, both of which may suffer from imperfections. In this comparison, the respective 2D cross-sections of calculated 3D complex valued wave fields distributions are presented. Also values of specific Gaussian beam parameters like full phase and Gouy phase shift and wave-front curvature radius are presented. The comparison between that form and the results of the angular spectrum algorithm brings information about the performance quality of that algorithm. [ABSTRACT FROM AUTHOR]

This research aims to make a comparison between the analytical and numerical methods of simulation of the Gaussian beam propagation in free space. This comparison brings evaluation of the accuracy and applicability limitations of the angular spectrum diffraction algorithm. In this approach, planar harmonic waves are assumed as basic components of a propagating wave, so the algorithm combines the angular spectrum technique and the 2D fast Fourier transformation procedures. It means a quite different approach than the well-established Huygens–Sommerfeld one, based on spherical waves. The Gaussian beam is a rare case of the exact analytical 3D solution of a specific wave diffraction problem, in paraxial scalar approximation. Gaussian beam form has been chosen here as an evaluation reference. It allows to avoid comparisons between two numerical procedures, both of which may suffer from imperfections. In this comparison, the respective 2D cross-sections of calculated 3D complex valued wave fields distributions are presented. Also values of specific Gaussian beam parameters like full phase and Gouy phase shift and wave-front curvature radius are presented. The comparison between that form and the results of the angular spectrum algorithm brings information about the performance quality of that algorithm. [ABSTRACT FROM AUTHOR]

This work quantitatively explores the dependence of the truncation errors on computational mesh settings for image-inclusion approaches and proposes a corresponding amendment. The new method is based on FFT algorithms and involves four individual portions. A mesh differential refinement scheme, consisting of independent and flexible selections-combinations of the surface, source, and target domains, is conceived to assist the proposed method. Comparisons of the results produced by the new and conventional mesh schemes demonstrate the significant improvements in computational performances. The new method can facilitate the numerical evaluation of local elastic characteristics caused by distributed inclusions or defects in contacting components. [ABSTRACT FROM AUTHOR]

The well-known k -nearest neighbors problem ( k NN ) involves building a data structure that reports the k closest training points to each of a given set of query points, with all points being in a given metric space S . The problem discussed here is an important operation in rotation-invariant image processing. It consists of a nontrivial variant of k NN : given a set of training points X and a set of query points Y find, for each query point y ∈ Y , the k nearest training points to y , where the notion of distance is given by a pseudometric of S defined over cyclic permutations of y and the elements of X . The multiplicity of the query point permutations makes serial brute force search too costly for instances of practical size. We present a transformation that enables any instance of the variant to be solved as a k NN problem. Although this enables the application of any k NN algorithm, the transformation is too time costly to be practical for instances of practical dimensions. For this reason, we present a condensation algorithm for the efficient elimination of unfavorable training points (that cannot be among the k closest neighbors of y ) and an effective parallel programming approach based on the discrete Fourier transform. The significant speedup gained over brute force search on practical datasets is reported. We also provide the mathematical basis of a conjecture that, if true, would enable the speedup to be significantly improved. The application of the approach to classification by support vector machines and k -means clustering is also discussed. [ABSTRACT FROM AUTHOR]

Numerical simulation of microstructure coarsening is a subject of great interest in computational materials science. The coarsening dynamics in a binary mixture can be modeled by the celebrated Cahn–Hilliard equations. To perform efficient and accurate long-time integrations, we develop a fast and stable high order numerical method for solving Cahn–Hilliard equations. The spatial discretization is carried out by the compact central difference scheme with FFT-based fast implementation while the time integration is done through the accurate exponential time differencing multistep approach. We demonstrate the effectiveness of the proposed method by numerical experiments and study computationally the coarsening kinetics corresponding to different choices of the diffusion mobility. [ABSTRACT FROM AUTHOR]

Improvements described consist of modifications of a composite fringe pattern in both frequency and direction of carrier fringes. Through these modified changes, the range of the measurable frequency under the scope of this study is increased nearly fourfold above its normal range. Theoretical and experimental results are presented. [ABSTRACT FROM AUTHOR]

Roll-to-roll (R2R) printing process is a key technology for achieving low-cost mass production of multilayer printed electronic devices. A register control, which maintains position accuracy between layers, is essential in the R2R multilayer printing process. In this study, a register control algorithm is developed to achieve microscale resolution in the register. The dominant factor behind machine direction register error is determined. Furthermore, an adequate register model is determined to estimate the register error according to tension disturbances. Permissible tension error is achieved for accomplishing the objective register and minimized for register control. The effect of the developed algorithm on the resolution of the register control is verified experimentally. Experimental results indicate that applying the proposed register algorithm achieved resolution below ±30 µm. This suggests that the proposed register algorithm is an essential application for a microscale resolution register. Finally, an application of the algorithm was introduced using examples considered in previous researches. [ABSTRACT FROM AUTHOR]

In this paper, we present algorithms for the approximation of multivariate periodic functions by trigonometric polynomials. The approximation is based on sampling of multivariate functions on rank-1 lattices. To this end, we study the approximation of periodic functions of a certain smoothness. Our considerations include functions from periodic Sobolev spaces of generalized mixed smoothness. Recently an algorithm for the trigonometric interpolation on generalized sparse grids for this class of functions was investigated by Griebel and Hamaekers (2014). The main advantage of our method is that the algorithm is based mainly on a single one-dimensional fast Fourier transform, and that the arithmetic complexity of the algorithm depends only on the cardinality of the support of the trigonometric polynomial in the frequency domain. Therefore, we investigate trigonometric polynomials with frequencies supported on hyperbolic crosses and energy norm based hyperbolic crosses in more detail. Furthermore, we present an algorithm for sampling multivariate functions on perturbed rank-1 lattices and show the numerical stability of the suggested method. Numerical results are presented up to dimension d = 10 , which confirm the theoretical findings. [ABSTRACT FROM AUTHOR]

The classic spectral representation method (SRM)-based nonstationary process simulation algorithm is used extensively in the engineering community. However, it is less efficient owing to the unavailability of fast Fourier transform (FFT). In this paper, an efficient, almost accurate, and straightforward algorithm is developed for the simulation of the multivariate nonstationary process. In this method, an evolutionary spectral matrix is decomposed via Cholesky method, and then proper orthogonal decomposition (POD) is used to factorize decomposed spectra as the summation of the products of time and frequency functions. Because original time-dependent decomposed spectra are decoupled via factorization, FFT can be used to significantly expedite the simulation efficiency. This POD-based factorization is totally data-driven and optimal, and fewer items are required in matching decomposed spectra. Therefore, the accuracy and efficiency of the factorization can be guaranteed at the same time. Another attractive feature of this factorization is straightforwardness, because only regular eigenvector decomposition is involved. Numerical examples of nonstationary processes are used to demonstrate the effectiveness and accuracy of the proposed approach. Results show that the factorization and simulation agree with the targets very well. In addition, the speed at which sample functions are generated is significantly improved over classic SRM, in which the full summation of sine/cosine terms is needed. [ABSTRACT FROM AUTHOR]