Search

Stochastic gradient descent algorithm is a classical and useful method for stochastic optimisation. While stochastic gradient descent has been theoretically investigated for decades and successfully applied in machine learning such as training of deep neural networks, it essentially relies on obtaining the unbiased estimates of gradients/subgradients of the objective functions. In this paper, by constructing the randomised differences of the objective function, a gradient‐free algorithm, named the stochastic randomised‐difference descent algorithm, is proposed for stochastic convex optimisation. Under the strongly convex assumption of the objective function, it is proved that the estimates generated from stochastic randomised‐difference descent converge to the optimal value with probability one, and the convergence rates of both the mean square error of estimates and the regret functions are established. Finally, some numerical examples are prsented. [ABSTRACT FROM AUTHOR]

Summary: This paper presents some recent advances for parallel‐in‐time methods applied to linear elasticity. With recent computer architecture changes leading to stagnant clock speeds, but ever increasing numbers of cores, future speedups will be available through increased concurrency. Thus, sequential algorithms, such as time stepping, will suffer a bottleneck. This paper explores multigrid reduction in time (MGRIT) for an important application area, linear elasticity. Previously, efforts at parallel‐in‐time for elasticity have experienced difficulties, for example, the beating phenomenon. As a result, practical parallel‐in‐time algorithms for this application area currently do not exist. This paper proposes some solutions made possible by MGRIT (e.g., slow temporal coarsening and FCF‐relaxation) and, more importantly, a different formulation of the problem that is more amenable to parallel‐in‐time methods. Using a recently developed convergence theory for MGRIT and Parareal, we show that the changed formulation of the problem avoids the instability issues and allows the reduction of the error using two temporal grids. We then extend our approach to the multilevel case, where we demonstrate how slow temporal coarsening improves convergence. The paper ends with supporting numerical results showing a practical algorithm enjoying speedup benefits over the sequential algorithm. [ABSTRACT FROM AUTHOR]

Reproducing kernel Hilbert space method is given for nonlinear boundary‐value problems in this paper. Applying this technique, we establish a new algorithm to approximate the solution of such nonlinear boundary‐value problems. This technique does not need any background mesh and can easily be applied. In this technique, the solution is given in the form of a series. Representation of the solutions is obtained in the reproducing kernel Hilbert space. Additionally, the convergence of the presented method is demonstrated. Numerical examples are presented to show the ability of the method. We compare the reproducing kernel Hilbert space method with B‐spline collocation method. As seen in the tables, the reproducing kernel Hilbert space method gives better results. [ABSTRACT FROM AUTHOR]

In this paper, the full discrete scheme of mixed finite element approximation is introduced for semilinear hyperbolic equations. To solve the nonlinear problem efficiently, two two‐grid algorithms are developed and analyzed. In this approach, the nonlinear system is solved on a coarse mesh with width H, and the linear system is solved on a fine mesh with width h≪H. Error estimates and convergence results of two‐grid method are derived in detail. It is shown that if we choose H = O ( h 1 3 ) in the first algorithm and H = O ( h 1 4 ) in the second algorithm, the two‐grid algorithms can achieve the same accuracy of the mixed finite element solutions. Finally, the numerical examples also show that the two‐grid method is much more efficient than solving the nonlinear mixed finite element system directly. [ABSTRACT FROM AUTHOR]

In this paper, a novel high-order optimal terminal iterative learning control (high-order OTILC) is proposed via a data-driven approach for nonlinear discrete-time systems with unknown orders in the input and output. The objective is to track the desired values at the endpoint of the operation cycle. The terminal tracking errors over more than one previous iterations are used to enhance the high-order OTILC's performance with faster convergence. From rigor of the analysis, the monotonic convergence of the terminal tracking error is proved along the iteration direction. More importantly, the condition for a high-order OTILC to outperform the low-order ones is first established by this work. The learning gain is not fixed but iteratively updated by using the input and output (I/O) data, which enhances the flexibility of the proposed controller for modifications and expansions. The proposed method is data-driven in which no explicit models are used except for the input and output data. The applications to a highly nonlinear continuous stirred tank reactor and a highly nonlinear fed-batch fermentater demonstrate the effectiveness of the proposed high-order OTILC design. [ABSTRACT FROM AUTHOR]

SUMMARY In a recent paper an algorithm for large-scale Tikhonov regularization in standard form called GKB-FP was proposed and numerically illustrated. In this paper, further insight into the convergence properties of this method is provided, and extensions to general-form Tikhonov regularization are introduced. In addition, as alternative to Tikhonov regularization, a preconditioned LSQR method coupled with an automatic stopping rule is proposed. Preconditioning seeks to incorporate smoothing properties of the regularization matrix into the computed solution. Numerical results are reported to illustrate the methods on large-scale problems. Copyright © 2013 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

Based on the extended extragradient-like method and the linesearch technique, we propose three projection methods for finding a common solution of a finite family of equilibrium problems. The linesearch used in the proposed algorithms has allowed to reduce some conditions imposed on equilibrium bifunctions. The strongly convergent theorems are established without the Lipschitz-type condition of bifunctions. The paper also helps in the design and analysis of practical algorithms and gives us a generalization of some previously known problems. Copyright © 2017 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

Our work is devoted to an inverse problem for three-dimensional parabolic partial differential equations. When the surface temperature data are given, the problem of reconstructing the heat flux and the source term is investigated. There are two main contributions of this paper. First, an adjoint problem approach is used for analysis of the Fréchet gradient of the cost functional. Second, an improved conjugate gradient method is proposed to solve this problem. Based on Lipschitz continuity of the gradient, the convergence analysis of the conjugate gradient algorithm is studied. Copyright © 2016 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

Lenstra-Lenstra-Lovász (LLL) is an effective lattice reduction algorithm for multiple-input multiple-output (MIMO) systems, which was considered to achieve full diversity in the MIMO fading channel. In the LLL algorithm, size reduction is performed for pairs of consecutive basis vectors, and the concern of numerical stability is raised. However, the whole complexity of the LLL algorithm is of polynomial order, and its characteristics of the convergence perform poor in MIMO system. In this paper, a variant version, named the novel hybrid algorithm, which combines both fix measurement and round measurement, is proposed. By modifying the iteration criterion and choosing proper values of the parameters, the algorithm has a large probability to skip the size reduction and cause a faster convergence, It means in one algorithm iteration the LLL potential can be reduced as much as possible. Also, the performance bound derived by the proximity factor shows that the hybrid LLL has a minor performance loss compared to the LLL algorithm. As a direct consequence, in simulation results, the hybrid LLL algorithm can make a better compromise between the rate of convergence, complexity of the algorithm, and algorithmic performance. © 2016 Institute of Electrical Engineers of Japan. Published by John Wiley & Sons, Inc. [ABSTRACT FROM AUTHOR]

The ChebFilterCG algorithm, proposed by Golub, Ruiz, and Touhami [SIAM J. Matrix Anal. Appl. 29 (2007), pp. 774-795] is an iterative method that combines Chebyshev filter and conjugate gradient for solving symmetric positive definite linear systems with multiple right-hand sides. The Chebyshev filter is used to produce initial residuals rich in eigenvectors corresponding to the smallest eigenvalues, which are then used in the initial phase of the conjugate gradient. This paper presents a convergence analysis of ChebFilterCG. In particular, it is shown theoretically and numerically that the algorithm yields an approximation of the invariant subspace associated with the smallest eigenvalues that can be recycled for solving several linear systems with the same matrix and different right-hand sides. A refined error bound when solving these systems is also given. The choice and influence of the Chebyshev filtering steps is discussed. Numerical experiments are described to illustrate that the Chebyshev filter does not degrade the distribution of the smallest eigenvalues and highlight the effect of rounding errors when large outlying eigenvalues are present. Finally, it is shown that the method may become more effective when an additional Chebyshev filtering step is used in the initialization phase of ChebFilterCG. [ABSTRACT FROM AUTHOR]

In this paper, we study an a posteriori error indicator introduced in E. Dari, R.G. Durán, and C. Padra, Appl. Numer. Math., 2012, for the approximation of the Laplace eigenvalue problem with Crouzeix-Raviart nonconforming finite elements. In particular, we show that the estimator is robust also in presence of eigenvalues of multiplicity greater than one. Some numerical examples confirm the theory and illustrate the convergence of an adaptive algorithm when dealing with multiple eigenvalues. Copyright © 2015 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

In this paper, we use recent results of Jarner & Roberts ( Ann. Appl. Probab., 12, 2002, 224) to show polynomial convergence rates of Monte Carlo Markov Chain algorithms with polynomial target distributions, in particular random-walk Metropolis algorithms, Langevin algorithms and independence samplers. We also use similar methodology to consider polynomial convergence of the Gibbs sampler on a constrained state space. The main result for the random-walk Metropolis algorithm is that heavy-tailed proposal distributions lead to higher rates of convergence and thus to qualitatively better algorithms as measured, for instance, by the existence of central limit theorems for higher moments. Thus, the paper gives for the first time a theoretical justification for the common belief that heavy-tailed proposal distributions improve convergence in the context of random-walk Metropolis algorithms. Similar results are shown to hold for Langevin algorithms and the independence sampler, while results for the mixing of Gibbs samplers on uniform distributions on constrained spaces are rather different in character. [ABSTRACT FROM AUTHOR]

This paper proposes a new algorithm for the unconstrained optimization problem, which is derived as an application of the control theory called Direct Gradient Descent Control. The static optimization problem is solved by using a dynamic controller in which the convergence speed can be greatly accelerated. The major idea is to consider the objective function F(x) and its time derivative dF(x(t))/dt as the evaluation criteria, and to apply the gradient descent method. It is verified by simulation that the proposed dynamic mathematical programming has a very great capability to converge to the optimal solution. It is also interesting to note that the method has to a certain extent the ability to find not only local optimal solutions, but also global optimal solutions. This paper improves the basic algorithm of dynamic mathematical programming so that it is suited to global optimization. The new algorithm generates movement toward the global optimal solution by utilizing two different trajectories with interaction (the chaotic trajectory and convergence trajectory). It is verified by simulation that the new algorithm functions as a global optimization procedure with a high success probability. © 2005 Wiley Periodicals, Inc. Electron Comm Jpn Pt 3, 88(6): 20–27, 2005; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/ecjc.20094 [ABSTRACT FROM AUTHOR]

Preconditioners based on various multilevel extensions of two-level finite element methods (FEM) lead to iterative methods which have an optimal order computational complexity with respect to the size of the system. Such methods were first presented in Axelsson and Padiy (SIAM. J. Sci. Stat. Comp. 1990; 20:1807) and Axelsson and Vassilevski (Numer. Math. 1989; 56:157), and are based on (recursive) two-level splittings of the finite element space. The key role in the derivation of optimal convergence rate estimates is played by the constant γ in the so-called Cauchy–Bunyakowski–Schwarz (CBS) inequality, associated with the angle between the two subspaces of the splitting. It turns out that only existence of uniform estimates for this constant is not enough but accurate quantitative bounds for γ have to be found as well. More precisely, the value of the upper bound for γ∈(0,1) is part of the construction of various multilevel extensions of the related two-level methods. In this paper, an algebraic two-level preconditioning algorithm for second-order elliptic boundary value problems is constructed, where the discretization is done using Crouzeix–Raviart non-conforming linear finite elements on triangles. An important point to make is that in this case the finite element spaces corresponding to two successive levels of mesh refinements are not nested. To handle this, a proper two-level basis is considered, which enables us to fit the general framework for the construction of two-level preconditioners for conforming finite elements and to generalize the method to the multilevel case. The major contribution of this paper is the derived estimates of the related constant γ in the strengthened CBS inequality. These estimates are uniform with respect to both coefficient and mesh anisotropy. To our knowledge, the results presented in the paper are the first such estimates for non-conforming FEM systems. Copyright © 2004 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

In this paper, we study a modified normalized least mean square (NLMS) algorithm for updating coefficients of an adaptive FIR digital filter (ADF). In the modified adaptive algorithm, filter coefficients are updated with the NLMS algorithm for each sample, but the coefficients are frozen when the input signal is smaller than a given threshold (constant). This modified NLMS has been known, but not been analyzed. In this paper, we call the modified NLMS the “conditioned NLMS” (C-NLMS) and analyze the convergence characteristics. As a result, the optimum threshold value is obtained. The simulation results and theoretical analyses show the effectiveness of the C-NLMS with the proposed threshold, and a good agreement between both results. The stability of the NLMS algorithm in the presence of a small input signal is improved. The convergence speed of the C-NLMS ADF under noisy circumstances is also faster than that of the unconditioned ordinary NLMS ADF in the small tap number case. © 2001 Scripta Technica, Electr Eng Jpn, 136(4): 47–57, 2001 [ABSTRACT FROM AUTHOR]

In this paper, we study a class of weakly nonlinear complementarity problems arising from the discretization of free boundary problems. By reformulating the complementarity problems as implicit fixed-point equations based on splitting of the system matrices, we propose a class of modulus-based matrix splitting algorithms. We show their convergence by assuming that the system matrix is positive definite. Moreover, we give several kinds of typical practical choices of the modulus-based matrix splitting iteration methods based on the different splitting of the system matrix. Numerical experiments on two model problems are presented to illustrate the theoretical results and examine the numerical effectiveness of our modulus-based matrix splitting algorithms. Copyright © 2016 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

It is known in the normalized least mean square (NLMS) algorithm that the convergence time can be reduced by applying a control in which the step gain is gradually reduced, as the estimation precision is improved. A problem in realizing this idea is that the instantaneous value of the estimation precision which is needed in the control of the step gain cannot be observed directly from the residual signal which contains external disturbances. This paper considers a block length control, which can be used in the “summational” NLMS method. The method is able to improve the convergence of the estimation precision, as in step gain control, and a method of reducing the convergence time is proposed, utilizing the fact that saturation of the convergence behavior can be observed iteratively by extending the block. In addition, it is highly likely in an actual adaptive system that the reference signal, the power of the external disturbance, and the impulse response of the unknown system to be estimated as the coefficients of the finite impulse response (FIR) filter will change. It is not realistic to ignore the possibility of these changes in discussing the control of convergence. In the last part of this paper, it is shown that the proposed control method can handle these changes. © 1999 Scripta Technica, Electron Comm Jpn Pt 3, 82(12): 54–64, 1999 [ABSTRACT FROM AUTHOR]

In this paper, the geometric learning algorithm (GLA) is proposed for an elementary perceptron which includes a single output neuron. The GLA is a modified version of the affine projection algorithm (APA) for adaptive filters. The weight update vector is determined geometrically with respect to the orthogonal complement of the k patterns to be classified, where k is the order of the GLA. In the case of the APA, the target of the coefficient update is a single point which corresponds to the best identification of the unknown system. On the other hand, in the case of the GLA, the target of the weight update is the area in which all of the given patterns are classified correctly. Thus, their convergence conditions are different. In this paper, the convergence condition of the first-order GLA for 2 patterns is derived theoretically. The condition is represented by the relation between the angle θ of 2 patterns and the learning rate λ. Next, the new concept of the angle ψmin of the solution area is introduced for the case of many patterns. Computer simulation results indicate that the relation between ψmin and λ for convergence can be approximated by the relation between θ and λ for 2 patterns. Furthermore, it is proved that the first-order GLA always converges regardless of the number of patterns when λ = 2. By our analysis and proof, the convergence of the first-order GLA is guaranteed and its usefulness as the learning algorithm is confirmed. The distributions of ψmin and λ for the convergence of the first-order GLA are approximately determined. © 1999 Scripta Technica, Electron Comm Jpn Pt 3, 82(9): 29–38, 1999 [ABSTRACT FROM AUTHOR]

As a method of solving the electromagnetic scattering by perfectly conducting cylinders, the discrete singularity method is discussed. For this method, a finite number of singular points is distributed within the scatterer and the wave function composed of a linear combination of solutions (each of which is derived from a helmholtz equation with each single singularity among the many) is matched with the incident wave function on the boundary. The remaining important problem in this method is how to distributed these singularities in order to obtain the accurate solution with faster convergence and with fewer number of singular points for an arbitrary configuration of the scatterer. The purpose of this paper is to present a reasonable solution to this problem. The essential of the method is that by making as unknown quantities, not only the unknown amplitude coefficients involved in the linear combination of the solutions, but also the coordinates of the singularities, the scattered wave is matched on the boundary in the sense of the least squares. This problem is linear in the amplitude coefficient but nonlinear in the singularity coordinate. Thus we solve this problem by using the algorithm by marquardt et al, of a nonlinear optimization process. This paper considers the general description and indicates its effectiveness by showing a few examples of the scattering problem of rectangular cylinders. [ABSTRACT FROM AUTHOR]

Recently, extensive studies have been carried out on the algorithms which constructively determine the solution of nonlinear equations, These algorithms are in general attraction lies in the global convergence. However, fixed-point algorithms have been a problem in the execution speed is decreased greatly with the increase of the size of the system of equations to consider. This paper proposes a decomposition method and acceleration techniques as a means to improve the computational efficiency of the fixed point algorithms. Kevorkian's method is used in this paper as decomposition. Since the method includes errors in the decomposed equations and function value, it is important to discuss the convergence of the solution algorithm and to improve the convergence speed taking the effect of the those errors into consideration. This paper shows a solution algorithm in which the system of equations is decomposed by Kevorkian's method, and then Merril's method, a typical fixed-point algorithm, is applied. Accuracy of simplicial approximation and convergence properties of the algorithm are discussed, indicating that the algorithm exhibits local quadratic convergence under some suitable conditions. By numerical examples, it is verified that the algorithm exhibits quadratic convergence. The method is compared with the past methods, indicating the effectiveness of the propose method. [ABSTRACT FROM AUTHOR]

SUMMARY In this paper, a rapid iterative algorithm is proposed to find robust approximations for the inverse of nonsingular matrices. The analysis of convergence reveals that this high-order method possesses eighth-order convergence. The interesting point is that, this rate is attained using less number of matrix-by-matrix multiplications in contrast to the existing methods of the same type in the literature. The extension of the method for finding Moore-Penrose inverse of singular or rectangular matrices is also presented. Numerical comparisons will be given to show the applicability, stability and consistency of the new scheme by paying special attention on the computational time. Copyright © 2013 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

SUMMARY In this paper, some important spectral characterizations of symmetric nonnegative tensors are analyzed. In particular, it is shown that a symmetric nonnegative tensor has the following properties: (i) its spectral radius is zero if and only if it is a zero tensor; (ii) it is weakly irreducible (respectively, irreducible) if and only if it has a unique positive (respectively, nonnegative) eigenvalue-eigenvector; (iii) the minimax theorem is satisfied without requiring the weak irreducibility condition; and (iv) if it is weakly reducible, then it can be decomposed into some weakly irreducible tensors. In addition, the problem of finding the largest eigenvalue of a symmetric nonnegative tensor is shown to be equivalent to finding the global solution of a convex optimization problem. Subsequently, algorithmic aspects for computing the largest eigenvalue of symmetric nonnegative tensors are discussed. Copyright © 2013 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

SUMMARY Convergence property of the iterative algorithm for Hammerstein or Wiener systems is generally hard to establish because of the existence the unmeasurable internal variables in such systems. In this paper, a fixed-point iteration is introduced to identifying both Hammerstein and Wiener systems with a unified algorithm. This newly proposed estimation algorithm gives consistent estimates under arbitrary nonzero initial conditions. In addition, the errors of the estimates are established as functions of the noise variance, and thus how the noise affects the quality of parameter estimates for a finite number of data points is made clear. Copyright © 2012 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

SUMMARY The choice of the preconditioner is a key factor to accelerate the convergence of eigensolvers for large-size sparse eigenproblems. Although incomplete factorizations with partial fill-in prove generally effective in sequential computations, the efficient preconditioning of parallel eigensolvers is still an open issue. The present paper describes the use of block factorized sparse approximate inverse (BFSAI) preconditioning for the parallel solution of large-size symmetric positive definite eigenproblems with both a simultaneous Rayleigh quotient minimization and the Jacobi-Davidson algorithm. BFSAI coupled with a block diagonal incomplete decomposition proves a robust and efficient parallel preconditioner in a number of test cases arising from the finite element discretization of 3D fluid-dynamical and mechanical engineering applications, outperforming FSAI even by a factor of 8 and exhibiting a satisfactory scalability. Copyright © 2011 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]

Newton iteration method can be used to find the minimal non-negative solution of a certain class of non-symmetric algebraic Riccati equations. However, a serious bottleneck exists in efficiency and storage for the implementation of the Newton iteration method, which comes from the use of some direct methods in exactly solving the involved Sylvester equations. In this paper, instead of direct methods, we apply a fast doubling iteration scheme to inexactly solve the Sylvester equations. Hence, a class of inexact Newton iteration methods that uses the Newton iteration method as the outer iteration and the doubling iteration scheme as the inner iteration is obtained. The corresponding procedure is precisely described and two practical methods of monotone convergence are algorithmically presented. In addition, the convergence property of these new methods is studied and numerical results are given to show their feasibility and effectiveness for solving the non-symmetric algebraic Riccati equations. Copyright © 2010 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

Nonlinear complementarity problem (NCP) is a wide class of problems. In this paper, some two-level additive Schwarz algorithms for NCPs with an M-function are developed and analyzed. The algorithms are proved to be convergent monotonically and can reach the solution of the problem within finite steps. They may also offer a possibility of making use of fast nonlinear solvers for solving the subproblems involved in the algorithms. Some preliminary numerical results are reported. Copyright © 2009 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

This paper presents some variants of the inexact Newton method for solving systems of nonlinear equations defined by locally Lipschitzian functions. These methods use variants of Newton's iteration in association with Krylov subspace methods for solving the Jacobian linear systems. Global convergence of the proposed algorithms is established under a nonmonotonic backtracking strategy. The local convergence based on the assumptions of semismoothness and BD-regularity at the solution is characterized, and the way to choose an inexact forcing sequence that preserves the rapid convergence of the proposed methods is also indicated. Numerical examples are given to show the practical viability of these approaches. Copyright © 2009 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

In this paper, a new channel assignment strategy named compact dynamic channel assignment (CDCA) is proposed. The CDCA differs from other strategies by consistently keeping the system in the utmost optimal state, and thus the scheme allows to determine a call succeeding or failing by local information instead of that of the whole network. It employs Hopfield neural networks for optimization which avoids the complicated assessment of channel compactness and guarantees optimum solutions for every assignment. A scheme based on Hopfield neural network is considered before; however, unlike others, in this algorithm an energy function is derived in such a way that for a neuron, the more a channel is currently being allocated in other cells, the more excitation the neuron will acquire, so as to guarantee each cluster using channels as few as possible. Performance measures in terms of the blocking probability, convergence rate and convergence time are obtained to assess the viability of the proposed scheme. Results presented show that the approach significantly reduces stringent requirements of searching space and convergence time. The algorithm is simple and straightforward, hence the efficient algorithm makes the real-time implementation of channel assignment based on neural network feasibility. Copyright © 2008 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

A new multigrid method based on high-order vector finite elements is proposed in this paper. Low-level discretizations in this method are obtained by using low-order vector finite elements for the same mesh. The Gauss–Seidel method is used as a smoother, and a linear equation of lowest level is solved by the ICCG method. But it is often found that multigrid solutions do not converge into ICCG solutions. An elimination algorithm of constant term using a null space of the coefficient matrix is also described. In three-dimensional magnetostatic field analysis, convergence time and number of iteration of this multigrid method are discussed with the conventional ICCG method. © 2009 Wiley Periodicals, Inc. Electron Comm Jpn, 92(1): 39–45, 2009; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/ecj.10228 [ABSTRACT FROM AUTHOR]

The integration step size is the main algorithmic parameter in time integration analysis. Nowadays, for time integration with the complete records of digitized excitations, the integration steps cannot be set larger than the excitation steps. Considering the practical importance of this restriction, and with the aim of structural dynamic analysis with less computational cost, this paper intends to extend conventional time integration analyses to analyses, if needed, carried out with steps larger than the excitations steps. In view of few simplifying assumptions, and presenting a new theorem on responses convergence, a technique is developed and a computational procedure is set. Being based on convergence-oriented redefinition of digitized excitations, the implementation of the new procedure is simple and, though, sacrificing some accuracy, can considerably reduce the total computational cost. Copyright © 2008 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

In 1979, Gay proved that Broyden's methods, when used for n-square linear systems, terminate in at most 2n iterations (SIAM J. Numer. Anal. 1979; 16:623–630). Also, the ABS methods were introduced in 1984 (Numer. Math. 1984; 45:1361–1376). In this paper we show another (handy) proof of Gay's theorem by these algorithms. Copyright © 2008 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

This paper considers the inexact Barzilai–Borwein (BB) algorithm applied to saddle point problems. To this aim, we study the convergence properties of the inexact BB algorithm for symmetric positive definite linear systems. Suppose that gk and &gtilde;k are the exact residual and its approximation of the linear system at the kth iteration, respectively. We prove the R-linear convergence of the algorithm if ∥&gtilde;k – gk∥⩽η∥&gtilde;k∥ for some small η>0 and all k. To adapt the algorithm for solving saddle point problems, we also extend the R-linear convergence result to the case when the right-hand term ∥&gtilde;k∥ is replaced by ∥&gtilde;k–1∥. Although our theoretical analyses cannot provide a good estimate to the parameter η, in practice, we find that η can be as large as the one in the inexact Uzawa algorithm. Further numerical experiments show that the inexact BB algorithm performs well for the tested saddle point problems. Copyright © 2007 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

In this paper, we present and analyse some local and parallel covolume algorithms for second-order elliptic problems. We first prove some local a priori error estimates for covolume method. With these results, we shall apply the two-grid strategy to covolume approximation to give two novel covolume algorithms, and show that the convergence rates of these algorithms are optimal in piecewise H1-norm. Numerical results confirming the theory are also provided. Copyright © 2005 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

Centroidal Voronoi tessellations (CVT) have diverse applications in many areas of science and engineering. The development of efficient algorithms for their construction is a key to their success in practice. In this paper, we study some new algorithms for the numerical computation of the CVT, including the Lloyd–Newton iteration and the optimization based multilevel method. Both theoretical analysis and computational simulations are conducted. Rigorous convergence results are presented and significant speedup in computation is demonstrated through the comparison with traditional methods. Copyright © 2006 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

The reference signals used in a multichannel system are usually strongly crosscorrelated. Preprocessing is normally added to reduce the crosscorrelation between the reference signals because this correlation makes estimating the adaptive filter coefficients difficult. However, this preprocessing is equivalent to warping the reference signals. The transmission of these warped reference signals to an unknown system hinders the essential system operation. On the other hand, it is necessary for uncorrelated components between the reference signals to exist when estimating the adaptive filter coefficients. Preprocessing that increases the ratio of these components is important in improving the convergence characteristics. In this paper, we propose an algorithm that does not transmit preprocessed reference signals to an unknown system, but only uses them to estimate the adaptive filter coefficients, and explain the design conditions needed to implement this algorithm. In other words, with the condition of not increasing the estimation errors, we derive the optimum values of the coefficients that reduce the correlation between the reference signals, which is a feature of this algorithm, and verify its effectiveness in simulations. By employing the proposed algorithm, improvements in the convergence characteristics can be designed without affecting the essential operation of the system. © 2004 Wiley Periodicals, Inc. Electron Comm Jpn Pt 3, 88(3): 32–41, 2005; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/ecjc.20092 [ABSTRACT FROM AUTHOR]

This paper analyses a novel method for constructing preconditioners for diagonally dominant symmetric positive-definite matrices. The method discussed here is based on a simple idea: we construct M by simply dropping offdiagonal non-zeros from A and modifying the diagonal elements to maintain a certain row-sum property. The preconditioners are extensions of Vaidya's augmented maximum-spanning-tree preconditioners. The preconditioners presented here were also mentioned by Vaidya in an unpublished manuscript, but without a complete analysis. The preconditioners that we present have only O(n+t2) nonzeros, where n is the dimension of the matrix and 1⩽t⩽n is a parameter that one can choose. Their construction is efficient and guarantees that the condition number of the preconditioned system is O(n2/t2) if the number of nonzeros per row in the matrix is bounded by a constant. We have developed an efficient algorithm to construct these preconditioners and we have implemented it. We used our implementation to solve a simple model problem; we show the combinatorial structure of the preconditioners and we present encouraging convergence results. [ABSTRACT FROM AUTHOR]

The standard multigrid algorithm is widely known to yield optimal convergence whenever all high-frequency error components correspond to large relative eigenvalues. This property guarantees that smoothers like Gauss–Seidel and Jacobi will significantly dampen all the high-frequency error components, and thus, produce a smooth error. This has been established for matrices generated from standard discretizations of most elliptic equations. In this paper, we address a system of equations that is generated from a perturbation of the non-elliptic operator I-grad div by a negative ℇ Δ. For ℇnear to one, this operator is elliptic, but as ℇapproaches zero, the operator becomes non-elliptic as it is dominated by its non-elliptic part. Previous research on the non-elliptic part has revealed that discretizing I-grad div with the proper finite element space allows one to define a robust geometric multigrid algorithm. The robustness of the multigrid algorithm depends on a relaxation operator that yields a smooth error. We use this research to assist in developing a robust discretization and solution method for the perturbed problem. To this end, we introduce a new finite element space for tensor product meshes that is used in the discretization, and a relaxation operator that succeeds in dampening all high-frequency error components. The success of the corresponding multigrid algorithm is first demonstrated by numerical results that quantitatively imply convergence for any ℇis bounded by the convergence for ℇequal to zero. Then we prove that convergence of this multigrid algorithm for the case of ℇ equal to zero is independent of mesh size. Copyright © 2004 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

In this paper, a novel preconditioner scheme slot neighbour (SN) preconditioner is applied to dense matrix equations derived from integral equations for a slot-array antenna in order to improve the convergence of iterative integral-equation solvers, such as the conjugate-gradient (CG) method. The preconditioner accounts for expansion-function–testing-function interactions in the vicinity of a given slot, requiring an order of Ns × Nb complexity for each Ns slot and each slot with Nb expansion unknowns. A typical slot-array antenna is analyzed and good results demonstrate the validity of the proposed algorithms. © 2003 Wiley Periodicals, Inc. Microwave Opt Technol Lett 37: 302–305, 2003; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/mop.10901 [ABSTRACT FROM AUTHOR]

An amplitude approaching algorithm (AAA) for the pattern synthesis of adaptive arrays is presented in this paper. Furthermore, the algorithm is amended by the Newton downhill method. Simulations show that the main lobe and side lobe can be controlled efficiently, and the algorithm converges more quickly and steadily. © 2003 Wiley Periodicals, Inc. Microwave Opt Technol Lett 36: 503–507, 2003; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/mop.10804 [ABSTRACT FROM AUTHOR]

In this paper, we study cutting plane methods for a Lagrangian relaxation-based unit commitment algorithm. In the algorithm, nondifferentiable optimization methods can be applied to optimize the dual function, and a subgradient method which needs parameter tuning and has some drawbacks such as computational inefficiency and oscillating behavior is commonly used. The cutting plane method and the central cutting plane method are applied to the algorithm and implemented using reoptimization techniques. A numerical example shows that both methods are accelerated by the reoptimization techniques and have good convergence without parameter tuning. © 2002 Wiley Periodicals, Inc. Electr Eng Jpn, 141(3): 17–29, 2002; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/eej.10066 [ABSTRACT FROM AUTHOR]

Additive Schwarz preconditioned GMRES is a powerful method for solving large sparse linear systems of equations on parallel computers. The algorithm is often implemented in the Euclidean norm, or the discrete l2 norm, however, the optimal convergence result is available only in the energy norm (or the equivalent Sobolev H1 norm). Very little progress has been made in the theoretical understanding of the l2 behaviour of this very successful algorithm. To add to the difficulty in developing a full l2 theory, in this note, we construct explicit examples and show that the optimal convergence of additive Schwarz preconditioned GMRES in l2 cannot be obtained using the existing GMRES theory. More precisely speaking, we show that the symmetric part of the preconditioned matrix, which plays a role in the Eisenstat–Elman–Schultz theory, has at least one negative eigenvalue, and we show that the condition number of the best possible eigenmatrix that diagonalizes the preconditioned matrix, key to the Saad–Schultz theory, is bounded from both above and below by constants multiplied by h-1/2. Here h is the finite element mesh size. The results presented in this paper are mostly negative, but we believe that the techniques used in our proofs may have wide applications in the further development of the l2 convergence theory and in other areas of domain decomposition methods. Copyright © 2002 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

We employ statistical dynamics to study the convergence of the Wake–Sleep (W-S) algorithm, which is a learning algorithm for neural network models having hidden units. Although there have been several reports on the effectiveness of the W-S algorithm based on experimental methods, the theoretical side is not clear even for a simple network. In this paper, we investigate the dynamic characteristics of the W-S algorithm expressed by a single factor analysis problem, which is the simplest state setting. The advantage of our approach is the ability to quantitatively evaluate the effect that the learning coefficients have on the convergence, which is difficult when using other methods. The result was that the settings of the learning coefficients, particularly in the Sleep step, had a substantial effect on the convergence of the algorithm. © 2001 Scripta Technica, Electron Comm Jpn Pt 3, 85(1): 41–49, 2002 [ABSTRACT FROM AUTHOR]

This paper presents an efficient solution for solving the generalized eigenvalue equation arising in the finite-element (FE) formulation of propagation characterization of planar transmission-line structures. A two-dimensional (2-D) finite-element method (FEM) is used for analyzing the uniform planar transmission lines. The Arnoldi algorithm is used in conjunction with the multifrontal decomposition of the system matrix for solving the eigensystem. Convergence is typically obtained within a few iterations of the Arnoldi process, and the formulation has proven to be robust, even when dealing with a significantly large number of unknowns. Numerical results are presented for the case of a uniform microstrip line, which clearly show the computational savings resulting from the use of the present approach. © 2001 John Wiley & Sons, Inc. Microwave Opt Technol Lett 31: 194–197, 2001. [ABSTRACT FROM AUTHOR]

This paper presents the new architecture of an adaptive predistortion linearizer. In the proposed linearizer, most of the processes, including the predistortion, are performed with a digital signal processor (DSP). The recursive least squares (RLS) algorithm is employed for the optimization process to minimize the errors between the predistorter and postdistorter output signals. Simulation results demonstrate that the spectral spreading is reduced by about 30 dB. The convergence and reconvergence performance of the linearizer is also satisfactory. © 2001 John Wiley & Sons, Inc. Microwave Opt Technol Lett 30: 283–286, 2001. [ABSTRACT FROM AUTHOR]

In this paper, we attempt to give analysis of the covolume method for solving general self-adjoint elliptic problems. We first present some useful superconvergence results for the deviation between the solution of the covolume method and the solution of the induced finite element method, in the energy norm and maximum norm, respectively. With these results, we then reproduce the maximum norm estimates obtained by Chou and Li for the covolume method easily. Furthermore, based on the covolume method, we propose a high-accuracy algorithm for solving general self-adjoint elliptic problems. Compared with the original covolume method, the computation work of the new algorithm is increased slightly, but the approximate error is improved remarkably. Copyright © 2001 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

It is important to get a steady-state operation of a power electronic circuit for its design. The shooting method, which is one of the steady-state analysis methods, solves a boundary value condition which equates initial values to final values after one-period transient. This paper proposes how to process the analysis in parallel by using a Parallel Virtual Machine (PVM3) system. In particular, the multiple shooting method (MSM) which divides the shooting time into subsections is suitable because it can parallel numerical processes for the divided shooting times by using multiple CPU units independently. This parallel method is applied to converter examples which are processes by PVM3. The computed results are investigated for their convergence and CPU times to check their parallel effects. According to the MSM algorithm, CPU times are reduced almost to one-fifth by using five computer units from a PVM3 system example. © 2001 Scripta Technica, Electr Eng Jpn, 135(2): 69–76, 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]

Recently the authors proposed a simultaneous iteration algorithm for the computation of the partial derivatives of repeated eigenvalues and the corresponding eigenvectors of matrices depending on several real variables. This paper analyses the properties of that algorithm and extends it in several ways. The previous requirement that the repeated eigenvalue be dominant is relaxed, and the new generalized algorithm given here allows the simultaneous treatment of simple and repeated eigenvalues. Methods for accelerating convergence are examined. Numerical results support our theoretical analysis. Copyright © 2000 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]