A second-order accurate three sub-step composite algorithm for structural dynamics

In this paper, a novel three sub-step composite algorithm with desired numerical properties is developed. The proposed method is a self-starting, unconditionally stable and second-order accurate implicit algorithm without overshoot. Particularly, the second-order accuracy in time is achieved in its final form, but it is not required in each sub-step. Its unique algorithmic parameter is analyzed to achieve the unconditional stability and it shares the identical effective stiffness matrix inside three sub-steps to save the computational cost in linear analyses. The same as the Bathe algorithm, the proposed algorithm is always L-stable, meaning that the spurious high-frequency modes can be effectively eliminated. Three numerical examples are simulated to illustrate the superiority of the proposed algorithm over some existing implicit algorithms. The first numerical simulation, solving a linear single-degree-of-freedom system, shows less period elongation errors and the second-order accuracy of the present scheme. The second one, a clamped-free bar excited by the end load, shows the ability of effectively damping out the unexpected high-frequency modes. The last example solves the nonlinear mass-spring system with variable degree-of-freedoms and illustrates that the composite sub-step algorithm can save more computational cost than the traditional implicit algorithm when the integration step size is selected appropriately.     

On the Numerical Solution to a Nonlinear Wave Equation Associated with the First Painlev′e Equation: an Operator-Splitting Approach

The main goal of this article is to discuss the numerical solution to a nonlinear wave equation associated with the first of the celebrated Painlevé transcendent ordinary differential equations. In order to solve numerically the above equation, whose solutions blow up in finite time, the authors advocate a numerical methodology based on the Strang’s symmetrized operator-splitting scheme. With this approach, one can decouple nonlinearity and differential operators, leading to the alternate solution at every time step of the equation as follows: (i) The first Painlevé ordinary differential equation, (ii) a linear wave equation with a constant coefficient. Assuming that the space dimension is two, the authors consider a fully discrete variant of the above scheme, where the space-time discretization of the linear wave equation sub-steps is achieved via a Galerkin/finite element space approximation combined with a second order accurate centered time discretization scheme. To handle the nonlinear sub-steps, a second order accurate centered explicit time discretization scheme with adaptively variable time step is used, in order to follow accurately the fast dynamic of the solution before it blows up. The results of numerical experiments are presented for different coefficients and boundary conditions. They show that the above methodology is robust and describes fairly accurately the evolution of a rather “violent” phenomenon.     

On numerical implementations of a new iterative method with boundary condition splitting for solving the nonstationary stokes problem in a strip with periodicity condition

Based on finite-difference approximations in time and a bilinear finite-element approximation in spatial variables, numerical implementations of a new iterative method with boundary condition splitting are constructed for solving the Dirichlet initial-boundary value problem for the nonstationary Stokes system. The problem is considered in a strip with a periodicity condition along it. At each iteration step of the method, the original problem splits into two much simpler boundary value problems that can be stably numerically approximated. As a result, this approach can be used to construct new effective and stable numerical methods for solving the nonstationary Stokes problem. The velocity and pressure are approximated by identical bilinear finite elements, and there is no need to satisfy the well-known difficult-to-verify Ladyzhenskaya-Brezzi-Babuska condition, as is usually required when the problem is discretized as a whole. Numerical iterative methods are constructed that are first- and second-order accurate in time and second-order accurate in space in the max norm for both velocity and pressure. The numerical methods have fairly high convergence rates corresponding to those of the original iterative method at the differential level (the error decreases approximately 7 times per iteration step). Numerical results are presented that illustrate the capabilities of the methods developed.     

Assessment of high-order discretization schemes for the DNS of compressible swirling mixing layers

We report on results of highly accurate Direct Numerical Simulations (DNS) solving the Navier-Stokes equations in cylindrical coordinates. The DNS code computes a compressible swirling mixing layer at Mach number Ma = 0.8. We present two simulations differing in the spatial discretization schemes for the convective terms. On the same grid, comparisons of flow simulations using different discretization schemes for otherwise identical conditions can be performed quantitatively and improve the understanding of the effects of numerical errors and in particular numerical dissipation. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Smoothing Newton algorithm for the second-order cone programming with a nonmonotone line search

The smoothing-type algorithms, which are in general designed based on some monotone line search, have been successfully applied to solve the second-order cone programming (denoted by SOCP). In this paper, we propose a nonmonotone smoothing Newton algorithm for solving the SOCP. Under suitable assumptions, we show that the proposed algorithm is globally and locally quadratically convergent. To compare with the existing smoothing-type algorithms for the SOCP, our algorithm has the following special properties: (i) it is based on a new smoothing function of the vector-valued natural residual function; (ii) it uses a nonmonotone line search scheme which contains the usual monotone line search as a special case. Preliminary numerical results demonstrate that the smoothing-type algorithm using the nonmonotone line search is promising for solving the SOCP.     

An algorithm for solving new trust region subproblem with conic model

The new trust region subproblem with the conic model was proposed in 2005, and was divided into three different cases. The first two cases can be converted into a quadratic model or a convex problem with quadratic constraints, while the third one is a nonconvex problem. In this paper, first we analyze the nonconvex problem, and reduce it to two convex problems. Then we discuss some dual properties of these problems and give an algorithm for solving them. At last, we present an algorithm for solving the new trust region subproblem with the conic model and report some numerical examples to illustrate the efficiency of the algorithm.     

Accurate solution of polynomial equations using Macaulay resultant matrices

We propose an algorithm for solving two polynomial equations in two variables. Our algorithm is based on the Macaulay resultant approach combined with new techniques, including randomization, to make the algorithm accurate in the presence of roundoff error. The ultimate computation is the solution of a generalized eigenvalue problem via the QZ method. We analyze the error due to roundoff of the method, showing that with high probability the roots are computed accurately, assuming that the input data (that is, the two polynomials) are well conditioned. Our analysis requires a novel combination of algebraic and numerical techniques.

     

Two-step relaxation Newton algorithm for solving nonlinear algebraic equations

We introduce a new algorithm, namely two-step relaxation Newton, for solving algebraic nonlinear equations f(x)=0. This new algorithm is derived by combining two different relaxation Newton algorithms introduced by Wu et al. (Appl. Math. Comput. 201:553–560, 2008), and therefore with special choice of the so called splitting function it can be implemented simultaneously, stably with much less memory storage and CPU time compared with the Newton–Raphson method. Global convergence of this algorithm is established and numerical experiments show that this new algorithm is feasible and effective, and outperforms the original relaxation Newton algorithm and the Newton–Raphson method in the sense of iteration number and CPU time.     

A new class of smoothing functions and a smoothing Newton method for complementarity problems

In this paper, we introduce a new class of smoothing functions, which include some popular smoothing complementarity functions. We show that the new smoothing functions possess a system of favorite properties. The existence and continuity of a smooth path for solving the nonlinear complementarity problem (NCP) with a P ₀ function are discussed. The Jacobian consistency of this class of smoothing functions is analyzed. Based on the new smoothing functions, we investigate a smoothing Newton algorithm for the NCP and discuss its global and local superlinear convergence. Some preliminary numerical results are reported.     

A family of new smoothing functions and?a?nonmonotone smoothing Newton method for?the?nonlinear complementarity problems

In this paper, based on a p-norm with p being any fixed real number in the interval (1,+??), we introduce a family of new smoothing functions, which include the smoothing symmetric perturbed Fischer function as a special case. We also show that the functions have several favorable properties. Based on the new smoothing functions, we propose a nonmonotone smoothing Newton algorithm for solving nonlinear complementarity problems. The proposed algorithm only need to solve one linear system of equations. We show that the proposed algorithm is globally and locally superlinearly convergent under suitable assumptions. Numerical experiments indicate that the method associated with a smaller p, for example p=1.1, usually has better numerical performance than the smoothing symmetric perturbed Fischer function, which exactly corresponds to p=2.     

Symmetric and Non-Symmetric ABS Methods for Solving Diophantine Systems of Equations

In the present paper we describe a new class of algorithms for solving Diophantine systems of equations in integer arithmetic. This algorithm, designated as the integer ABS (iABS) algorithm, is based on the ABS methods in the real space, with extensive modifications to ensure that all calculations remain in the integer space. Importantly, the iABS solves Diophantine systems of equations without determining the Hermite normal form. The algorithm is suitable for solving determined, over- or underdetermined, full rank or rank deficient linear integer equations. We also present a scaled integer ABS system and two special cases for solving general Diophantine systems of equations. In the scaled symmetric iABS (ssiABS), the Abaffian matrix H _i is symmetric, allowing that only half of its elements need to be calculated and stored. The scaled non-symmetric iABS system (snsiABS) provides more freedom in selecting the arbitrary parameters and thus the maximal values of H _i can be maintained at a certainly lower level. In addition to the above theoretical results, we also provide numerical experiments to test the performance of the ssiABS and the snsiABS algorithms. These experiments have confirmed the suitability of the iABS system for practical applications.     

AN EFFECTIVE SEQUENTIAL QUADRATIC PROGRAMMING ALGORITHM FOR NONLINEAR OPTIMIZATION PROBLEMS

In this paper,a new globally convergent algorithm for nonlinear optimization prablems with equality and inequality constraints is presented. The new algorithm is of SQP type which determines a search direction by solving a quadratic programming subproblem per itera-tion. Some revisions on the quadratic programming subproblem have been made in such a way that the associated constraint region is nonempty for each point x generated by the algorithm, i. e. , the subproblems always have optimal solutions. The new algorithm has two important properties. The computation of revision parameter for guaranteeing the consistency of quadratic sub-problem and the computation of the second order correction step for superlinear convergence use the same inverse of a matrix per iteration, so the computation amount of the new algorithm will not be increased much more than other SQP type algorithms; Another is that the new algorithm can give automatically a feasible point as a starting point for the quadratic subproblems pe     

Error analysis and preconditioning for an enhanced DtN-FE algorithm for exterior scattering problems

In this paper we present an error analysis for a high-order accurate combined Dirichlet-to-Neumann (DtN) map/finite element (FE) algorithm for solving two-dimensional exterior scattering problems. We advocate the use of an exact DtN (or Steklov–Poincaré) map at an artificial boundary exterior to the scatterer to truncate the unbounded computational region. The advantage of using an exact DtN map is that it provides a transparent condition which does not reflect scattered waves unphysically. Our algorithm allows for the specification of quite general artificial boundaries which are perturbations of a circle. To compute the DtN map on such a geometry we utilize a boundary perturbation method based upon recent theoretical work concerning the analyticity of the DtN map. We also present some preliminary work concerning the preconditioning of the resulting system of linear equations, including numerical experiments.     

A column generation based decomposition algorithm for a parallel machine just-in-time scheduling problem

We propose a column generation based exact decomposition algorithm for the problem of scheduling n jobs with an unrestrictively large common due date on m identical parallel machines to minimize total weighted earliness and tardiness. We first formulate the problem as an integer program, then reformulate it, using Dantzig–Wolfe decomposition, as a set partitioning problem with side constraints. Based on this set partitioning formulation, a branch and bound exact solution algorithm is developed for the problem. In the branch and bound tree, each node is the linear relaxation problem of a set partitioning problem with side constraints. This linear relaxation problem is solved by column generation approach where columns represent partial schedules on single machines and are generated by solving two single machine subproblems. Our computational results show that this decomposition algorithm is capable of solving problems with up to 60 jobs in reasonable cpu time.     

A polynomially solvable case of the three machine johnson problem

Under study is the classical NP-hard problem with three machines: N tasks must be fulfilled at three machines in minimum time. The processing time is given of each task at each machine. The processing sequences of all tasks are identical. It is impossible to process two tasks at one machine at the same time. We address the properties of this problem, find a new polynomially solvable case, and discuss a corresponding algorithm.     

Discrete and continuous maximum principles for parabolic and elliptic operators

The major qualitative properties of linear parabolic and elliptic operators/PDEs are the different maximum principles (MPs). Another important property is the stabilization property (SP), which connects these two types of operators/PDEs. This means that under some assumptions the solution of the parabolic PDE tends to an equilibrium state when t→∞, which is the solution of the corresponding elliptic PDE. To solve PDEs we need to use some numerical methods, and it is a natural requirement that these qualitative properties are preserved on the discrete level. In this work we investigate this question when a two-level discrete mesh operator is used as the discrete model of the parabolic operator (which is a one-step numerical procedure for solving the parabolic PDE) and a matrix as a discrete elliptic operator (which is a linear algebraic system of equations for solving the elliptic PDE). We clarify the relation between the discrete parabolic maximum principle (DPMP), the discrete elliptic maximum principle (DEMP) and the discrete stabilization property (DSP). The main result is that the DPMP implies the DSP and the DEMP.     

A study of truly incompressible and weakly compressible Smoothed Particle Hydrodynamics methods to model incompressible flows with free surfaces

The Smoothed Particle Hydrodynamics (SPH) method is a meshless discretization method for solving, e.g., the Navier-Stokes equations. By now, it is used for hydraulic problems as well as for solid bodies. In general, there are two distinguishable approaches for incompressible fluid flows. One is called weakly compressible SPH (WCSPH) and the other is called truly incompressible SPH (ISPH). The main difference between these two approaches is the way of pressure evaluation. In WCSPH, a state equation is used, while in ISPH the pressure Poisson equation is solved. Each approach has its advantages as well as its disadvantages, for example the complexity of the numerical algorithm for WCSPH is smaller than for ISPH, but the pressure field is more accurate for ISPH. In this work, two representative examples are studied. The simulations were performed with two different codes, one developed at the Institute of Engineering and Computational Mechanics and one at the Institute of Chemical Process Engineering. It is the aim of this work to show some properties of WCSPH and ISPH as well as to compare two different implementations that, in detail, are very complex. (© 2014 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

A two-grid algorithm based on Newton iteration for the stream function form of the Navier-Stokes equations

In this paper, we propose a two-grid algorithm for solving the stream function formulation of the stationary Navier-Stokes equations. The algorithm is constructed by reducing the original system to one small, nonlinear system on the coarse mesh space and two similar linear systems (with same stiffness matrix but different right-hand side) on the fine mesh space. The convergence analysis and error estimation of the algorithm are given for the case of conforming elements. Furthermore, the algorithm produces a numerical solution with the optimal asymptotic H ²-error. Finally, we give a numerical illustration to demonstrate the effectiveness of the two-grid algorithm for solving the Navier-Stokes equations.     

Numerical method for the simultaneous determination of the hydraulic properties of unsaturated porous media

This paper presents a numerical algorithm for solving the inverse coefficient problem for nonlinear parabolic equations. This problem arises in simultaneous determination of the hydraulic properties of unsaturated porous media from a simple outflow experiment. The novel feature of the method is that it is not based on output least squares. In this method, the unknown functions are represented as polygons (continuous and piecewise linear functions) every new linear pieces that are determined in each time step by using information based only on previous time intervals. The results of some numerical experiments are displayed.     

A smoothing and regularization Broyden-like method for nonlinear inequalities

In this paper, we consider the smoothing and regularization Broyden-like algorithm for the system of nonlinear inequalities. By constructing a new smoothing function $\phi(\mu,a)=\frac{1}{2}(a+\mu(\ln2+\ln(1+\cosh\frac{a}{\mu})))$ , the problem is approximated via a family of parameterized smooth equations H(μ,ε,x)=0. A smoothing and regularization Broyden-like algorithm with a non-monotone linear search is proposed for solving the system of nonlinear inequalities based on the new smoothing function. The global convergence of the algorithm is established under suitable assumptions. In addition, the smoothing parameter μ and the regularization parameter ε in our algorithm are viewed as two different independent variables. Preliminary numerical results show the efficiency of the algorithm and reveal that the regularization parameter ε in our algorithm plays an important role in numerical improvement, hence, our algorithm seems to be simpler and more easily implemented compared to many previous methods.