On inexact alternating direction implicit iteration for continuous Sylvester equations

In this paper, we study the alternating direction implicit (ADI) iteration for solving the continuous Sylvester equation AX + XB = C , where the coefficient matrices A and B are assumed to be positive semi‐definite matrices (not necessarily Hermitian), and at least one of them to be positive definite. We first analyze the convergence of the ADI iteration for solving such a class of Sylvester equations, then derive an upper bound for the contraction factor of this ADI iteration. To reduce its computational complexity, we further propose an inexact variant of the ADI iteration, which employs some Krylov subspace methods as its inner iteration processes at each step of the outer ADI iteration. The convergence is also analyzed in detail. The numerical experiments are given to illustrate the effectiveness of both ADI and inexact ADI iterations.     

Efficient Simulation of Wave Propagation with Implicit Finite Difference Schemes

Finite difference method is an important methodology in the approximation of waves. In this paper, we will study two implicit finite difference schemes for the simulation of waves. They are the weighted alternating direction implicit (ADI) scheme and the locally one-dimensional (LOD) scheme. The approximation errors, stability conditions, and dispersion relations for both schemes are investigated. Our analysis shows that the LOD implicit scheme has less dispersion error than that of the ADI scheme. Moreover, the unconditional stability for both schemes with arbitrary spatial accuracy is established for the first time. In order to improve computational efficiency, numerical algorithms based on message passing interface (MPI) are implemented. Numerical examples of wave propagation in a three-layer model and a standard complex model are presented. Our analysis and comparisons show that both ADI and LOD schemes are able to efficiently and accurately simulate wave propagation in complex media.     

Bifurcations of ordinary differential equations of Clairaut type

We classify a one-parameter family of Clairaut-type equations. In order to pursue the classification, we use legendrian singularity theory and the notion of one-parameter complete legendrian unfoldings which induces a special class of divergent diagrams of map germs which are called one-parameter integral diagrams. Our normal forms are represented by one-parameter integral diagrams.     

Fourth-Order Splitting Methods for Time-Dependant Differential Equations

This study was suggested by previous work on the simulation of evolution equations with scale-dependent processes,e.g.,wave-propagation or heat-transfer,that are modeled by wave equations or heat equations.Here,we study both parabolic and hyperbolic equations.We focus on ADI (alternating direction implicit) methods and LOD (locally one-dimensional) methods,which are standard splitting methods of lower order,e.g.second-order.Our aim is to develop higher-order ADI methods,which are performed by Richardson extrapolation,Crank-Nicolson methods and higher-order LOD methods,based on locally higher-order methods.We discuss the new theoretical results of the stability and consistency of the ADI methods.The main idea is to apply a higher- order time discretization and combine it with the ADI methods.We also discuss the dis- cretization and splitting methods for first-order and second-order evolution equations. The stability analysis is given for the ADI method for first-order time derivatives and for the LOD (locally one-dimensional) methods for second-order time derivatives.The higher-order methods are unconditionally stable.Some numerical experiments verify our results.     

Low rank methods for a class of generalized Lyapunov equations and related issues

In this paper, we study possible low rank solution methods for generalized Lyapunov equations arising in bilinear and stochastic control. We show that under certain assumptions one can expect a strong singular value decay in the solution matrix allowing for low rank approximations. Since the theoretical tools strongly make use of a connection to the standard linear Lyapunov equation, we can even extend the result to the $d$ -dimensional case described by a tensorized linear system of equations. We further provide some reasonable extensions of some of the most frequently used linear low rank solution techniques such as the alternating directions implicit (ADI) iteration and the Krylov-Plus-Inverted-Krylov (K-PIK) method. By means of some standard numerical examples used in the area of bilinear model order reduction, we will show the efficiency of the new methods.     

A class of three-point root-solvers of optimal order of convergence

The construction of a class of three-point methods for solving nonlinear equations of the eighth order is presented. These methods are developed by combining fourth order methods from the class of optimal two-point methods and a modified Newton’s method in the third step, obtained by a suitable approximation of the first derivative based on interpolation by a nonlinear fraction. It is proved that the new three-step methods reach the eighth order of convergence using only four function evaluations, which supports the Kung-Traub conjecture on the optimal order of convergence. Numerical examples for the selected special cases of two-step methods are given to demonstrate very fast convergence and a high computational efficiency of the proposed multipoint methods. Some computational aspects and the comparison with existing methods are also included.     

Compensating for order variation in mesh refinement for direct transcription methods II: computational experience

The numerical theory for Implicit Runge Kutta methods shows that there can be order reduction when these methods are applied to either stiff or differential algebraic equations. A previous paper introduced a way to try and compensate for this order reduction in designing mesh refinement strategies. This paper presents the results from a number of computational studies on the effectiveness of this approach. In addition, we present a new test problem which can be used to examine the efficiency of codes developed for a particular class of applications.     

An exponential high‐order compact ADI method for 3D unsteady convection–diffusion problems

In this article, we develop an exponential high order compact alternating direction implicit (EHOC ADI) method for solving three dimensional (3D) unsteady convection–diffusion equations. The method, which requires only a regular seven‐point 3D stencil similar to that in the standard second‐order methods, is second order accurate in time and fourth‐order accurate in space and unconditionally stable. The resulting EHOC ADI scheme in each alternating direction implicit (ADI) solution step corresponding to a strictly diagonally dominant matrix equation can be solved by the application of the one‐dimensional tridiagonal Thomas algorithm with a considerable saving in computing time. Numerical experiments for three test problems are carried out to demonstrate the performance of the present method and to compare it with the classical Douglas–Gunn ADI method and the Karaa's high‐order compact ADI method. © 2012 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 2013     

A comparative study of ADI splitting methods for parabolic equations in two space dimensions

The main purpose of the paper is a numerical comparison of three integration methods for semi-discrete parabolic partial differential equations in two space variables. Linear as well as nonlinear,equations are considered. The integration methods are the well-known ADI method of Peaceman and Rachford, a global extrapolation scheme of the classical ADI method to order four and a fourth order, four-step ADI splitting method.     

Combined bound-grid-factor constraints for enhancing RLT relaxations for polynomial programs

This paper studies the global optimization of polynomial programming problems using Reformulation-Linearization Technique (RLT)-based linear programming (LP) relaxations. We introduce a new class of bound-grid-factor constraints that can be judiciously used to augment the basic RLT relaxations in order to improve the quality of lower bounds and enhance the performance of global branch-and-bound algorithms. Certain theoretical properties are established that shed light on the effect of these valid inequalities in driving the discrepancies between RLT variables and their associated nonlinear products to zero. To preserve computational expediency while promoting efficiency, we propose certain concurrent and sequential cut generation routines and various grid-factor selection rules. The results indicate a significant tightening of lower bounds, which yields an overall reduction in computational effort for solving a test-bed of polynomial programming problems to global optimality in comparison with the basic RLT procedure as well as the commercial software BARON.     

Two-stage and Three-stage Diagonally Implicit Runge-Kutta Nystrom Methods of Orders Three and Four

We investigate the existence of two-stage and three-stage R-stable,P-stable, RL-stable, and dispersively enhanced diagonally implicitRunge-Kutta Nyström methods of orders three and four. Wefirst show that a one-parameter family of two-stage third-orderR-stable diagonally implicit methods exists, and that theirdispersive order is at most four. From this we show that two-stagefourth-order R-stable, and third-order P-stable and RL-stablediagonally implicit methods do not exist. Next we show a two-parameterfamily of three-stage fourth-order R-stable diagonally implicitmethods exists with dispersive order at most four, and thatthis family contains a one-parameter family of P-stable methodsand a unique RL-stable. We also show that a one-parameter familyof fourth-order diagonally implicit methods with dispersiveorder at least six exists, and that they are not R-stable. Wepresent third- and fourth-order R-stable and P-stable methodswith small principal truncation coefficients and discuss howthese methods might be implemented in an efficient integrator.     

Supervised learning algorithms for multi-class classification problems with partial class memberships

In several application domains such as biology, computer vision, social network analysis and information retrieval, multi-class classification problems arise in which data instances not simply belong to one particular class, but exhibit a partial membership to several classes. Existing machine learning or fuzzy set approaches for representing this type of fuzzy information mainly focus on unsupervised methods. In contrast, we present in this article supervised learning algorithms for classification problems with partial class memberships, where class memberships instead of crisp class labels serve as input for fitting a model to the data. Using kernel logistic regression (KLR) as a baseline method, first a basic one-versus-all approach is proposed, by replacing the binary-coded label vectors with [0,1]-valued class memberships in the likelihood. Subsequently, we use this KLR extension as base classifier to construct one-versus-one decompositions, in which partial class memberships are transformed and estimated in a pairwise manner. Empirical results on synthetic data and a real-world application in bioinformatics confirm that our approach delivers promising results. The one-versus-all method yields the best computational efficiency, while the one-versus-one methods are preferred in terms of predictive performance, especially when the observed class memberships are heavily unbalanced.     

New higher-order methods for the simultaneous inclusion of polynomial zeros

Higher-order methods for the simultaneous inclusion of complex zeros of algebraic polynomials are presented in parallel (total-step) and serial (single-step) versions. If the multiplicities of each zeros are given in advance, the proposed methods can be extended for multiple zeros using appropriate corrections. These methods are constructed on the basis of the zero-relation of Gargantini’s type, the inclusion isotonicity property and suitable corrections that appear in two-point methods of the fourth order for solving nonlinear equations. It is proved that the order of convergence of the proposed methods is at least six. The computational efficiency of the new methods is very high since the acceleration of convergence order from 3 (basic methods) to 6 (new methods) is attained using only n polynomial evaluations per iteration. Computational efficiency of the considered methods is studied in detail and two numerical examples are given to demonstrate the convergence behavior of the proposed methods.     

New filled functions for nonsmooth global optimization

The filled function method is an effective approach to find a global minimizer for a general class of nonsmooth programming problems with a closed bounded domain. This paper gives a new definition for the filled function, which overcomes some drawbacks of the previous definition. It proposes a two-parameter filled function and a one-parameter filled function to improve the efficiency of numerical computation. Based on these analyses, two corresponding filled function algorithms are presented. They are global optimization methods which modify the objective function as a filled function, and which find a better local minimizer gradually by optimizing the filled function constructed on the minimizer previously found. Numerical results obtained indicate the efficiency and reliability of the proposed filled function methods.     

An assessment of two approaches to variable metric methods

Two recent suggestions in the field of variable metric methods for function minimization are reviewed: the self-scaling method, first introduced by Oren and Luenberger, and the method of Biggs. The two proposals are considered both from a theoretical and computational aspect. They are compared with methods which use correction formulae from the Broyden one-parameter family, in particular the BFGS formula and the Fletcher switching strategy.     

A note on the improved derivative free root-solvers

Using a fixed point relation of the square-root type and the basic fourth-order method, improved methods of fifth and sixth order for the simultaneous determination of simple zeros of a polynomial are obtained. An increase in convergence is achieved without additional numerical operations, which points to high computational efficiency of the accelerated methods. The main aim of this work is the convergence analysis of improved simultaneous methods given under computationally verifiable initial conditions in the spirit of Smale’s point estimation theory.     

A technique to choose the most efficient method between secant method and some variants

A few variants of the secant method for solving nonlinear equations are analyzed and studied. In order to compute the local order of convergence of these iterative methods a development of the inverse operator of the first order divided differences of a function of several variables in two points is presented using a direct symbolic computation. The computational efficiency and the approximated computational order of convergence are introduced and computed choosing the most efficient method among the presented ones. Furthermore, we give a technique in order to estimate the computational cost of any iterative method, and this measure allows us to choose the most efficient among them.     

On a family of high-order iterative methods under gamma conditions with applications in denoising

We study a class of at least third order iterative methods for nonlinear equations on Banach spaces. A characterization of the convergence under Gamma-type conditions is presented. Though, in general, these methods are not very extended due to their computational costs, we can find examples in which they are competitive and even cheaper than other simpler methods. Indeed, we propose a new nonlinear mathematical model for the denoising of digital images, where the best method in the family has fourth order of convergence. Moreover, our family includes two-step Newton type methods with good numerical behavior in general. We center our analysis in both, analytic and computational, aspects.     

两类五阶解非线性方程组的迭代算法

本文首先根据Runge-Kutta方法的思想,结合Newton迭代法,提出了一类带参数的解非线性方程组F(x)=0的迭代算法,然后基于解非线性方程f(x)=0的King算法,给出第二类解非线性方程组的迭代算法,收敛性分析表明这两类算法都是五阶收敛的.其次给出了本文两类算法的效率指数,以及一些已知算法的效率指数,并且将本文算法的效率指数与其它方法进行详细的比较,通过效率比率R_(i,j)可知本文算法具有较高的计算效率.最后给出了四个数值实例,将本文两类算法与现有的几种算法进行比较,实验结果说明本文算法收敛速度快,迭代次数少,有明显的优势.     

Higher order symplectic RK and RKN methods using perturbed collocation

In this paper, we derive a one-parameter family of symplectic Runge-Kutta-Nyström methods of order 2s-1 and a two-parameter family of symplectic Runge-Kutta methods of order 2s-2.