Search

Summary: This paper studies a low‐communication algorithm for solving elliptic PDEs on high‐performance machines, the nested iteration with range decomposition (NIRD) algorithm. Previous work has shown that NIRD converges to a high level of accuracy within a small, fixed number of iterations (usually one or two) when applied to simple elliptic problems. This paper makes some improvements to the NIRD algorithm (including the addition of adaptivity during preprocessing, wider choice of partitioning functions, and modified error measurement) that enhance the method's accuracy and scalability, especially on more difficult problems. In addition, an updated convergence proof is presented based on heuristic assumptions that are supported by numerical evidence. Furthermore, a new performance model is developed that shows increased performance benefits for NIRD when problems are more expensive to solve using traditional methods. Finally, extensive testing on a variety of elliptic problems provides additional insight into the behavior of NIRD and additional evidence that NIRD achieves excellent convergence on a wide class of elliptic PDEs and, as such, should be a very competitive method for solving PDEs on large parallel computers. [ABSTRACT FROM AUTHOR]

In this paper, a surrogate‐based iterative importance sampling (IS) method is proposed to efficiently evaluate failure probability (FP) of engineering structures. The surrogate is constructed by the training points centered at the most probable failure point (MPP), which is estimated by an approximate algorithm without any additional evaluations of the real limit state function (LSF), and the IS method using the estimated MPP is further obtained; and an iterative procedure combined with the surrogate and the IS method is finally proposed to improve the accuracy of the estimated result for the FP. Three numerical examples are employed to demonstrate the accuracy of the proposed method, and further, an inside flap of an aircraft is employed to demonstrate the practical application of the proposed method in engineering problems. The results show that the reasonable estimated result of the FP within the range of 10−3‐10−5 can be evaluated by the proposed method with only hundreds of the evaluations of the real LSF. [ABSTRACT FROM AUTHOR]

This paper deals with the problem of finding minimum-norm fixed point of nonexpansive mappings. We present two types of iteration methods (one is implicit, and the other is explicit). We establish strong convergence theorems for both methods. Some applications are given regarding convex optimization problems and split feasibility problems. These results improve some known results existing in the literatures. Copyright © 2013 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

SUMMARY An iterative method for finding the largest eigenvalue of a nonnegative tensor was proposed by Ng, Qi, and Zhou in 2009. In this paper, we establish an explicit linear convergence rate of the Ng-Qi-Zhou method for essentially positive tensors. Numerical results are given to demonstrate linear convergence of the Ng-Qi-Zhou algorithm for essentially positive tensors. Copyright © 2011 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

SUMMARY In this paper, a practical two-term acceleration algorithm is proposed, the interval of the parameter which guarantees the convergence of the acceleration algorithm is analyzed in detail. Further, the acceleration ratio of the new acceleration algorithm is obtained in advance. The new acceleration algorithm is less sensitive to the parameter than the Chebyshev semi-iterative method. Finally, some numerical examples show that the accelerated algorithm is effective. Copyright © 2011 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

IDR ( s) is a family of fast algorithms for iteratively solving large nonsymmetric linear systems. With cluster computing and in particular with Grid computing, the inner product is a bottleneck operation. In this paper, three techniques are investigated for alleviating this bottleneck. First, a recently proposed IDR ( s) algorithm that is highly efficient and stable is reformulated in such a way that it has a single global synchronization point per iteration step. Second, the so-called test matrix is chosen so that the work, communication, and storage involving this matrix is minimized in multi-cluster environments. Finally, a methodology is presented for a-priori estimation of the optimal value of s using only problem and machine-based parameters. Numerical experiments applied to a 3D convection-diffusion problem are performed on the DAS-3 Grid computer, demonstrating the effectiveness of our approach. Copyright © 2011 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

The main advantage of inverse iteration over the QR algorithm and Divide & Conquer for the symmetric tridiagonal eigenproblem is that subsets of eigenpairs can be computed at reduced cost. The MRRR algorithm (MRRR = multiple relatively robust representations) is a clever variant of inverse iteration without the need for reorthogonalization. STEGR, the current version of MRRR in LAPACK 3.0, does not allow for subset computations. The next release of STEGR is designed to compute a (sub-)set of k eigenpairs with O (kn) operations. Because of the special way in which eigenvectors are computed, MRRR subset computations are more complicated than when using inverse iteration. Unlike the latter, MRRR sometimes cannot ignore the unwanted part of the spectrum. We describe the problems with what we call 'false singletons'. These are eigenvalues that appear to be isolated with respect to the wanted eigenvalues but in fact belong to a tight cluster of unwanted eigenvalues. This paper analyses these complications and ways to deal with them. Published in 2006 by John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

In this paper, we propose a new adaptive filter and adaptive nonlinear predictor to implement the nonlinear prediction of speech signals to solve the problem of impulse-shaped residual errors in the linear prediction. While using order statistics processing, we add an improvement that keeps time information about the input signal to the LMS-L filter proposed by Pitas and Venetsanopoulos. Tests using synthesized speech show that the proposed nonlinear predictor has superior prediction performance to the Volterra series predictor and not just the linear predictor. However, even with this proposed nonlinear predictor, the prediction accuracy degrades in experiments using real speech. Therefore, we propose a new iterative method to conquer this problem. The iterative method pays attention to the periodicity of the speech, reuses the speech data, and obtains a prediction accuracy similar to when using many data samples. In experiments on real continuous speech, the proposed predictor improved prediction accuracy by using the iterative method, and the effectiveness of the method was confirmed. © 2005 Wiley Periodicals, Inc. Electron Comm Jpn Pt 3, 88(11): 28–42, 2005; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/ecjc.20148 [ABSTRACT FROM AUTHOR]

Many problems in image restoration can be formulated as either an unconstrained non-linear minimization problem, usually with a Tikhonov-like regularization, where the regularization parameter has to be determined; or as a fully constrained problem, where an estimate of the noise level, either the variance or the signal-to-noise ratio, is available. The formulations are mathematically equivalent. However, in practice, it is much easier to develop algorithms for the unconstrained problem, and not always obvious how to adapt such methods to solve the corresponding constrained problem. In this paper, we present a new method which can make use of any existing convergent method for the unconstrained problem to solve the constrained one. The new method is based on a Newton iteration applied to an extended system of non-linear equations, which couples the constraint and the regularized problem, but it does not require knowledge of the Jacobian of the irregularity functional. The existing solver is only used as a black box solver, which for a fixed regularization parameter returns an improved solution to the unconstrained minimization problem given an initial guess. The new modular solver enables us to easily solve the constrained image restoration problem; the solver automatically identifies the regularization parameter, during the iterative solution process. We present some numerical results. The results indicate that even in the worst case the constrained solver requires only about twice as much work as the unconstrained one, and in some instances the constrained solver can be even faster. Copyright © 2002 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

Dispersed generators (DGs) such as fuel cells and solar cells will be installed on the demand side of power systems. Such dispersed facilities can reduce distribution system loss by appropriate allocation. Planning and operation of distribution systems with the dispersed facilities have already been discussed. In this paper, the authors discuss the extent to which distribution system loss can be reduced if DGs are optimally allocated on the demand side of the distribution system. In order to determine the optimal allocation and size of DGs so as to minimize the distribution system loss, an algorithm based on tabu search is employed. The proposed algorithm consists of iterated nested use of the tabu search algorithm. Namely, in the proposed algorithm, in one computational iteration, after the location of the DG is temporarily determined by tabu search, the size of the DG is also determined by tabu search so as to minimize the distribution system loss for the temporarily determined allocation. Numerical simulations are carried out for two system models in order to examine the validity of the algorithm. © 2001 Scripta Technica, Electr Eng Jpn, 136(2): 1–8, 2001 [ABSTRACT FROM AUTHOR]

The translation matrix for the multilevel fast multipole algorithm (MLFMA) in an FISC (fast Illinois solver code) is calculated directly, and the complexity is O(N3/2), where N is the number of unknowns. For a problem with a small electrical size, the CPU time for calculating the translation matrix can be negligible. But for large problems, the calculation time increases significantly. In this paper, we use interpolation to calculate the translation matrix, and the complexity is reduced to O(N). Different interpolation techniques are tested, and it is found that the Lagrange polynomial interpolation with high sampling rates is the best. The saving factor is 10 for the VFY218 at 4 GHz. © 2001 John Wiley & Sons, Inc. Microwave Opt Technol Lett 30: 109–114, 2001. [ABSTRACT FROM AUTHOR]

The DEFLATED-GMRES(m, k) method is one of the major iterative solvers for the large sparse linear systems of equations, x = b. This algorithm assembles a preconditioner adaptively for the GMRES(m) method based on eigencomponents gathered from the Arnoldi process during iterations. It is usually known that if a restarted GMRES(m) method is used to solve linear systems of equations, the information of the smallest eigencomponents is lost at each restart and the super-linear convergence may also be lost. In this paper, we propose an adaptive procedure that combines the DEFLATED-GMRES(m, k) algorithm and the determination of a restart frequency automatically. It is shown that a new algorithm combining elements of both will reduce the negative effects of the restarted procedure. The numerical experiments are presented on three test problems by using the MIMD parallel machine AP3000. From these numerical results, we show that the proposed algorithm leads to faster convergence than the conventional DEFLATED-GMRES(m, k) method. Copyright © 2000 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

In a previous work, the generalized forward–backward (GFB) method was proposed to compute the scattering from targets on rough ocean-like surfaces. In this paper, we develop an acceleration of the GFB method based on the fast multipole method (FMM). The FMM is adapted to reduce the operational cost associated with the iterative computations in the target regions. The proposed method is shown to converge in a low number of iterations, and allows a significant reduction in the computational and storage costs with respect to the conventional GFB formulation. © 2000 John Wiley & Sons, Inc. Microwave Opt Technol Lett 26: 78–83, 2000. [ABSTRACT FROM AUTHOR]

Given convex scattered data in R3 we consider the constrained interpolation problem of finding a smooth, minimal Lp-norm (1 < p < ∞) interpolation network that is convex along the edges of an associated triangulation. In previous work the problem has been reduced to the solution of a nonlinear system of equations. In this paper we formulate and analyse a Newton-type algorithm for solving the corresponding type of systems. The correctness of the application of the proposed method is proved and its superlinear (in some cases quadratic) convergence is shown. Copyright © 2000 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

This paper shows the ability of a domain decomposition method with a Neumann-Neumann preconditioner to solve industrial and biomechanical problems. For a mid-size biomedical simulation involving soft tissues the results obtained by using this algorithm are comapred to those obtained by more classical methods. The present algorithm thus appears to be more reliable than standard iterative methods and more efficient than a direct method. Copyright © 1999 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

When a formant is modified based on the pole of the AR model, a problem arises due to the interaction between the pole to be modified and other poles such as the apparent elimination of the formant, if the frequency of the considered pole simply is modified. To solve this problem, the method proposed in this paper uses the spectral intensity at the pole frequency as a new future parameter and the spectral intensity at the pole after the frequency modification is corrected to the desired value by iterative processings. To examine the effectiveness of the proposed method, an experiment was conducted in which a phoneme in a word is replaced into the same phoneme in a different environment, and then the format frequency is modified by the proposed method in order to restore the original speech. The speeches before and after the modification are compared in terms of the cepstral distance (CD) from the original speech, and it is verified that the proposed method is effective in the modification of the formant. An attempt is made to solve the formant discontinuity problem at the concatenation point in waveform based speech synthesis-by-rule and to modify the formant frequency accompanying the modification of the fundamental frequency using the proposed method. It was verified as a result of experiment that the speech after formant modification is better than the speech before modification, indicating that the proposed method is useful in improving the quality of the synthesized speech. [ABSTRACT FROM AUTHOR]

This paper presents a general method to associate the operator splitting for the Peaceman-Rachford procedure with a decomposition of the domain in problems arising from finite element discretization of partial differential equations. The algorithm is provably convergent without any symmetry requirement. Moreover, this method possesses the significant advantage of making the linear systems of the Peaceman-Rachford iteration block diagonal and therefore perfectly appropriate for parallel processing. Not only is sparsity not affected but a reduction of the bandwidth occurs. In fact, for appropriate choices of nonconforming finite element spaces, this method makes directly possible elementwise processing. This option remains available in general for higher-dimensional problems by applying the splitting algorithm recursively. Practical implementation requires nothing more than the standard finite element assembly procedure and some bookkeeping to relate a few different orderings of the nodes. In addition to all these attractive features, the method is rapidly convergent and remains highly competitive even when used on a serial machine. [ABSTRACT FROM AUTHOR]

The solution of nonsymmetric systems of linear equations continues to be a difficult problem. A main algorithm for solving nonsymmetric problems is restarted GMRES. The algorithm is based on restarting full GMRES every s iterations, for some integer s > 0. This paper considers the impact of the restart frequency s on the convergence and work requirements of the method. It is shown that a good choice of this parameter can lead to reduced solution time, while an improper choice may hinder or preclude convergence. An adaptive procedure is also presented for determining automatically when to restart. The results of numerical experiments are presented. [ABSTRACT FROM AUTHOR]

In the paper the author presents a novel point of view for the refinement and derefinement algorithms of triangular nested meshes using fractal concepts and iterated function systems (IFS). The fractal behaviour can be understood in the sense that these meshes feature a remarkable amplifying invariance under changes of magnification. Here we compare the meshes obtained by the combination of these algorithms with those presented by Bova and Carey (1992). Although both of the meshes are very similar, the current algorithms automatically build and manage sequences of nested irregular discretizations of the domain. The author illustrates here how the application of IFS families is equivalent to the use of an adaptive strategy that combines the refinement procedure with the derefinement one. [ABSTRACT FROM AUTHOR]

In the paper [1], a direct version of the classical Kaczmarz algorithm was proposed, which gives us in only one iteration a solution of an arbitrary consistent system of linear equations. Unfortunately, as any direct method applied to large sparse matrices, this algorithm is based on some modifications of the system matrix sparsity structure such that a big fill-in appears. In order to overcome this difficulty, in the present paper we propose a modified version of this direct Kaczmarz algorithm in which the transformations applied to the system matrix try to conserve the initial sparsity structure. This transformations are done via clustering using Jaccard and Hamming distances. The modified Kaczmarz algorithm is no more a direct method, but we obtain an acceleration of convergence with respect to the classical Kaczmarz algorithm. Numerical experiments which ilustrate the efficiency of our algorithm are also presented. (© 2013 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim) [ABSTRACT FROM AUTHOR]