An algorithm for computing Bingham flows

A three-parameter iterative method for computing Bingham flows is examined. The method is a generalization of the well-known Arrow-Hurwicz algorithm. The local convergence of the method is proved.     

A minimum-stencil difference scheme for computing two-dimensional axisymmetric gas flows: Examples of pulsating flows with instabilities

A minimum-stencil difference scheme for computing two-dimensional axisymmetric gas flows is described. The scheme is explicit, conservative, and second-order accurate in space and time. The numerical results obtained for pulsating flows and contact discontinuity instabilities are discussed. The mechanisms of flow pulsation and instability generation are described.     

A fast minimal residual algorithm for shifted unitary matrices

A new iterative scheme is described for the solution of large linear systems of equations with a matrix of the form A = ρU + ζI, where ρ and ζ are constants, U is a unitary matrix and I is the identity matrix. We show that for such matrices a Krylov subspace basis can be generated by recursion formulas with few terms. This leads to a minimal residual algorithm that requires little storage and makes it possible to determine each iterate with fairly little arithmetic work. This algorithm provides a model for iterative methods for non-Hermitian linear systems of equations, in a similar way to the conjugate gradient and conjugate residual algorithms. Our iterative scheme illustrates that results by Faber and Manteuffel [3,4] on the existence of conjugate gradient algorithms with short recurrence relations, and related results by Joubert and Young [13], can be extended.     

A variant of the finite superelement method for computing viscous incompressible flows

A variant of the finite superelement method (FSEM) is proposed for computing viscous incompressible convection-dominated flows on a triangular unstructured mesh. To construct the high-order FSEM scheme, vector polynomial test functions (SE basis) are calculated in each grid cell by solving the linearized Navier-Stokes equations with special boundary conditions in the form of basis functions in the trace space.     

A globally convergent inexact Newton method with a new choice for the forcing term

In inexact Newton methods for solving nonlinear systems of equations, an approximation to the step s _k of the Newton’s system J(x _k )s=−F(x _k ) is found. This means that s _k must satisfy a condition like ‖F(x _k )+J(x _k )s _k ‖≤η _k ‖F(x _k )‖ for a forcing term η _k ∈[0,1). Possible choices for η _k have already been presented. In this work, a new choice for η _k is proposed. The method is globalized using a robust backtracking strategy proposed by Birgin et al. (Numerical Algorithms 32:249–260, 2003), and its convergence properties are proved. Several numerical experiments with boundary value problems are presented. The numerical performance of the proposed algorithm is analyzed by the performance profile tool proposed by Dolan and Moré (Mathematical Programming Series A 91:201–213, 2002). The results obtained show a competitive inexact Newton method for solving academic and applied problems in several areas. Supported by FAPESP, CNPq, PRONEX-Optimization.     

A polynomial cycle canceling algorithm for submodular flows

Submodular flow problems, introduced by Edmonds and Giles [2], generalize network flow problems. Many algorithms for solving network flow problems have been generalized to submodular flow problems (cf. references in Fujishige [4]), e.g. the cycle canceling method of Klein [9]. For network flow problems, the choice of minimum-mean cycles in Goldberg and Tarjan [6], and the choice of minimum-ratio cycles in Wallacher [12] lead to polynomial cycle canceling methods. For submodular flow problems, Cui and Fujishige [1] show finiteness for the minimum-mean cycle method while Zimmermann [16] develops a pseudo-polynomial minimum ratio cycle method. Here, we prove pseudo-polynomiality of a larger class of the minimum-ratio variants and, by combining both methods, we develop a polynomial cycle canceling algorithm for submodular flow problems. Received July 22, 1994 / Revised version received July 18, 1997? Published online May 28, 1999     

A fast algorithm for computing minimum 3-way and 4-way cuts

For an edge-weighted graph G with n vertices and m edges, we present a new deterministic algorithm for computing a minimum k-way cut for k=3,4. The algorithm runs in O(n ^k-1 F(n,m))=O(mn ^k log(n ² /m)) time and O(n ²) space for k=3,4, where F(n,m) denotes the time bound required to solve the maximum flow problem in G. The bound for k=3 matches the current best deterministic bound ?(mn ³) for weighted graphs, but improves the bound ?(mn ³) to O(n ² F(n,m))=O(min{mn ^8/3,m ^3/2 n ²}) for unweighted graphs. The bound ?(mn ⁴) for k=4 improves the previous best randomized bound ?(n ⁶) (for m=o(n ²)). The algorithm is then generalized to the problem of finding a minimum 3-way cut in a symmetric submodular system. Received: April 1999 / Accepted: February 2000?Published online August 18, 2000     

A globally convergent interval method for computing and bounding real roots

In this paper, we extend the interval Newton method to the case where the interval derivative may contain zero. This extended method will isolate and bound all the real roots of a continuously differentiable function in a given interval. In particular, it will bound multiple roots. We prove that the method never fails to converge.     

A relaxation Riemann solver for compressible two-phase flow with phase transition and surface tension

The dynamics of two-phase flows depend crucially on interfacial effects like surface tension and phase transition. A numerical method for compressible inviscid flows is proposed that accounts in particular for these two effects. The approach relies on the solution of Riemann-like problems across the interface that separates the liquid and the vapour phase. Since the analytical solutions of the Riemann problems are only known in particular cases an approximative Riemann solver for arbitrary settings is constructed. The approximative solutions rely on the relaxation technique.The local well-posedness of the approximative solver is proven. Finally we present numerical experiments for radially symmetric configurations that underline the reliability and efficiency of the numerical scheme.     

An exact Riemann solver and a Godunov scheme for simulating highly transient mixed flows

The current research aims at deriving a one-dimensional numerical model for describing highly transient mixed flows. In particular, this paper focuses on the development and assessment of a unified numerical scheme adapted to describe free-surface flow, pressurized flow and mixed flow (characterized by the simultaneous occurrence of free-surface and pressurized flows). The methodology includes three steps. First, the authors derived a unified mathematical model based on the Preissmann slot model. Second, a first-order explicit finite volume Godunov-type scheme is used to solve the set of equations. Third, the numerical model is assessed by comparison with analytical, experimental and numerical results. The key results of the paper are the development of an original negative Preissmann slot for simulating sub-atmospheric pressurized flow and the derivation of an exact Riemann solver for the Saint-Venant equations coupled with the Preissmann slot.     

A meshless method based on boundary integral equations and radial basis functions for biharmonic-type problems

This paper presents a meshless method, which replaces the inhomogeneous biharmonic equation by two Poisson equations in terms of an intermediate function. The solution of the Poisson equation with the intermediate function as the right-hand term may be written as a sum of a particular solution and a homogeneous solution of a Laplace equation. The intermediate function is approximated by a series of radial basis functions. Then the particular solution is obtained via employing Kansa’s method, while the homogeneous solution is approximated by using the boundary radial point interpolation method by means of boundary integral equations. Besides, the proposed meshless method, in conjunction with the analog equation method, is further developed for solving generalized biharmonic-type problems. Some numerical tests illustrate the efficiency of the method proposed.     

A meshless numerical approach based on Integrated Radial Basis Functions and level set method for interfacial flows

This paper reports a new meshless Integrated Radial Basis Function Network (IRBFN) approach to the numerical simulation of interfacial flows in which the two-way interaction between a moving interface and the ambient viscous flow is fully investigated. When an interface between two immiscible fluids moves, not only its position and shape but also the flow variables (i.e. velocity field and pressure) change due to the presence of surface tension along the moving interface. The velocity field of the ambient flow, on the other hand, causes the interface to move and deform as a result of momentum transport between the two immiscible fluids on both sides of the interface. Numerical investigations of such a two-way interaction is reported in this paper where the level set method is used in combination with high-order projection schemes in the meshless framework of the IRBFN method. Numerical investigations on the meshless projection schemes are performed with typical benchmark incompressible viscous flow problems for verification purposes. The approach is then demonstrated with the numerical simulation of two bubbles moving, stretching and merging in an incompressible ambient fluid under the action of buoyancy force.     

凝析油-气两相流偏微分方程组问题的求解及应用

根据凝析气藏开发的实际需要，引入凝析油－气两相拟压力、拟时间函数，建立了凝析气在双重渗透率介质中的不稳定渗流新模型，该模型为一类偏微分方程组的混合问题，本文研究了这类偏微分方程组问题的求解方法。     

A fast finite difference method for biharmonic equations on irregular domains and its application to an incompressible Stokes flow

Biharmonic equations have many applications, especially in fluid and solid mechanics, but is difficult to solve due to the fourth order derivatives in the differential equation. In this paper a fast second order accurate algorithm based on a finite difference discretization and a Cartesian grid is developed for two dimensional biharmonic equations on irregular domains with essential boundary conditions. The irregular domain is embedded into a rectangular region and the biharmonic equation is decoupled to two Poisson equations. An auxiliary unknown quantity Δu along the boundary is introduced so that fast Poisson solvers on irregular domains can be used. Non-trivial numerical examples show the efficiency of the proposed method. The number of iterations of the method is independent of the mesh size. Another key to the method is a new interpolation scheme to evaluate the residual of the Schur complement system. The new biharmonic solver has been applied to solve the incompressible Stokes flow on an irregular domain.      

A comprehensive simplex-like algorithm for network optimization and perturbation analysis

The family of network optimization problems includes the following prototype models: assignment, critical path, max flow, shortest path, and transportation. Although it is long known that these problems can be modeled as linear programs (LP), this is generally not done. Due to the relative inefficiency and complexity of the simplex methods (primal, dual, and other variations) for network models, these problems are usually treated by one of over 100 specialized algorithms. This leads to several difficulties. The solution algorithms are not unified and each algorithm uses a different strategy to exploit the special structure of a specific problem. Furthermore, small variations in the problem, such as the introduction of side constraints, destroys the special structure and requires modifying andjor restarting the algorithm. Also, these algorithms obtain solution efficiency at the expense of managerial insight, as the final solutions from these algorithms do not have sufficient information to perform postoptimality analysis.

Another approach is to adapt the simplex to network optimization problems through network simplex. This provides unification of the various problems but maintains all the inefficiencies of simplex, as well as, most of the network inflexibility to handle changes such as side constraints. Even ordinary sensitivity analysis (OSA), long available in the tabular simplex, has been only recently transferred to network simplex.

This paper provides a single unified algorithm for all five network models. The proposed solution algorithm is a variant of the self-dual simplex with a warm start. This algorithm makes available the full power of LP perturbation analysis (PA) extended to handle optimal degeneracy. In contrast to OSA, the proposed PA provides ranges for which the current optimal strategy remains optimal, for simultaneous dependent or independent changes from the nominal values in costs, arc capacities, or suppliesJdemands. The proposed solution algorithm also facilitates incorporation of network structural changes and side constraints. It has the advantage of being computationally practical, easy for managers to understand and use, and provides useful PA information in all cases. Computer implementation issues are discussed and illustrative numerical examples are provided in the Appendix     

ABS methods and ABSPACK for linear systems and optimization: A review

ABS methods are a large class of methods, based upon the Egervary rank reducing algebraic process, first introduced in 1984 by Abaffy, Broyden and Spedicato for solving linear algebraic systems, and later extended to nonlinear algebraic equations, to optimization problems and other fields; software based upon ABS methods is now under development. Current ABS literature consists of about 400 papers. ABS methods provide a unification of several classes of classical algorithms and more efficient new solvers for a number of problems. In this paper we review ABS methods for linear systems and optimization, from both the point of view of theory and the numerical performance of ABSPACK.Work partially supported by ex MURST 60% 2001 funds.E. Spedicato     

A family of iterative methods for computing the approximate inverse of a square matrix and inner inverse of a non-square matrix

Based on a quadratical convergence method, a family of iterative methods to compute the approximate inverse of square matrix are presented. The theoretical proofs and numerical experiments show that these iterative methods are very effective. And, more importantly, these methods can be used to compute the inner inverse and their convergence proofs are given by fundamental matrix tools.     

A numerical method for mass conservative coupling between fluid flow and solute transport

We present a new coupled discretization approach for species transport in an incompressible fluid. The Navier-Stokes equations for the flow are discretized by the divergence-free Scott-Vogelius element on barycentrically refined meshes guaranteeing LBB stability. The convection-diffusion equation for species transport is discretized by the Voronoi finite volume method. In accordance to the continuous setting, due to the exact integration of the normal component of the flow through the Voronoi surfaces, the species concentration fulfills discrete global and local maximum principles. Besides of the numerical scheme itself, we present important aspects of its implementation. Further, for the case of homogeneous Dirichlet boundary conditions, we give a convergence proof for the coupled scheme. We report results of the application of the scheme to the interpretation of limiting current measurements in an electrochemical flow cell with cylindrical shape.     

A B-differentiable equation-based,globally and locally quadratically convergent algorithm for nonlinear programs,complementarity and variational inequality problems

This paper presents a globally convergent, locally quadratically convergent algorithm for solving general nonlinear programs, nonlinear complementarity and variational inequality problems. The algorithm is based on a unified formulation of these three mathematical programming problems as a certain system of B-differentiable equations, and is a modification of the damped Newton method described in Pang (1990) for solving such systems of nonsmooth equations. The algorithm resembles several existing methods for solving these classes of mathematical programs, but has some special features of its own; in particular, it possesses the combined advantage of fast quadratic rate of convergence of a basic Newton method and the desirable global convergence induced by one-dimensional Armijo line searches. In the context of a nonlinear program, the algorithm is of the sequential quadratic programming type with two distinct characteristics: (i) it makes no use of a penalty function; and (ii) it circumvents the Maratos effect. In the context of the variational inequality/complementarity problem, the algorithm provides a Newton-type descent method that is guaranteed globally convergent without requiring the F-differentiability assumption of the defining B-differentiable equations.This work was based on research supported by the National Science Foundation under Grant No. ECS-8717968.