A boundary preserving numerical algorithm for the Wright-Fisher model with mutation

The Wright-Fisher model is an It? stochastic differential equation that was originally introduced to model genetic drift within finite populations and has recently been used as an approximation to ion channel dynamics within cardiac and neuronal cells. While analytic solutions to this equation remain within the interval [0,1], current numerical methods are unable to preserve such boundaries in the approximation. We present a new numerical method that guarantees approximations to a form of Wright-Fisher model, which includes mutation, remain within [0,1] for all time with probability one. Strong convergence of the method is proved and numerical experiments suggest that this new scheme converges with strong order 1/2. Extending this method to a multidimensional case, numerical tests suggest that the algorithm still converges strongly with order 1/2. Finally, numerical solutions obtained using this new method are compared to those obtained using the Euler-Maruyama method where the Wiener increment is resampled to ensure solutions remain within [0,1].     

A study of a numerical algorithm for a nonlinear transport model

For a nonlinear transport model, we propose a simple and economical two-step algorithm that decreases the dimension of the system of nonlinear equations, as compared with implicit difference schemes. We prove theorems on necessary conditions for stability with respect to the initial data for the nonlinear problem and theorems on sufficient conditions for stability in the case of the linearized model. We also obtain theorems on approximation of the integral conservation law on a grid. The necessary condition obtained is a condition on the coefficients of the differential equation (which singles out an admissible class of equations) but not a condition on the ratio of the grid steps. Bibliography: 3 titles. Translated fromObchyslyuval'na ta Prykladna Matematyka, No. 81, 1997, pp. 25–32.     

A Bayesian algorithm for global optimization

A crucial step in global optimization algorithms based on random sampling in the search domain is decision about the achievement of a prescribed accuracy. In order to overcome the difficulties related to such a decision, the Bayesian Nonparametric Approach has been introduced. The aim of this paper is to show the effectiveness of the approach when an ad hoc clustering technique is used for obtaining promising starting points for a local search algorithm. Several test problems are considered.     

Memetic algorithm for the antibandwidth maximization problem

The antibandwidth maximization problem (AMP) consists of labeling the vertices of a n-vertex graph G with distinct integers from 1 to n such that the minimum difference of labels of adjacent vertices is maximized. This problem can be formulated as a dual problem to the well known bandwidth problem. Exact results have been proved for some standard graphs like paths, cycles, 2 and 3-dimensional meshes, tori, some special trees etc., however, no algorithm has been proposed for the general graphs. In this paper, we propose a memetic algorithm for the antibandwidth maximization problem, wherein we explore various breadth first search generated level structures of a graph—an imperative feature of our algorithm. We design a new heuristic which exploits these level structures to label the vertices of the graph. The algorithm is able to achieve the exact antibandwidth for the standard graphs as mentioned. Moreover, we conjecture the antibandwidth of some 3-dimensional meshes and complement of power graphs, supported by our experimental results.     

A sequentially optimal algorithm for numerical integration

For the class of functions of one variable, satisfying the Lipschitz condition with a fixed constant, an optimal passive algorithm for numerical integration (an optimal quadrature formula) has been found by Nikol'skii. In this paper, a sequentially optimal algorithm is constructed; i.e., the algorithm on each step makes use in an optimal way of all relevant information which was accumulated on previous steps. Using the algorithm, it is necessary to solve an integer program at each step. An effective algorithm for solving these problems is given.The author is indebted to Professor S. E. Dreyfus, Department of Industrial Engineering and Operations Research, University of California, Berkeley, California, for his helpful attention to this paper.     

A model for understanding numerical stability

^** Email: bornemann{at}ma.tum.de We present a model of roundoff error analysis that combinessimplicity with predictive power. Though not considering allsources of roundoff within an algorithm, the model is relatedto a recursive roundoff error analysis and therefore is capableof correctly predicting stability or instability of an algorithm.By means of nontrivial examples, such as the componentwise backwardstability analysis of Gaussian elimination with a single iterativerefinement step, we demonstrate that the model even yields quantitativebackward error bounds that show all the known problem-dependentterms with the exception of dimension-dependent constants. Themodel can serve as a convenient tool for teaching or as a heuristicdevice to discover stability results before entering a furtherdetailed analysis.     

A numerical model for magnetic chromatography

In this paper, we present details of a mathematical model for magnetic chromatography (MC) systems where strong distorted magnetic fields are used to separate particles from a colloidal mixture. The model simulates the effect of magnetic field gradients on particle motion, and includes calculation of the fluid flow, magnetic field, and particle concentration field. It is based on the finite-volume method (FVM) and uses an expanding-grid technique to handle domains with large aspect ratios. The model has been validated against the results from an analytical model. The numerical model has been used to simulate the performance of a real MC system under various operating conditions.     

A bisection algorithm for the numerical Mountain Pass

We propose a constructive proof for the Ambrosetti-Rabinowitz Mountain Pass Theorem providing an algorithm, based on a bisection method, for its implementation. The efficiency of our algorithm, particularly suitable for problems in high dimensions, consists in the low number of flow lines to be computed for its convergence; for this reason it improves the one currently used and proposed by Y.S. Choi and P.J. McKenna in [3]. Susanna Terracini: This work is partially supported by M.I.U.R. project “Metodi Variazionali ed Equazioni Differenziali Nonlineari”.     

A distributionally robust area under curve maximization model

Area under ROC curve (AUC) is a performance measure for classification models. We propose new distributionally robust AUC models (DR-AUC) that rely on the Kantorovich metric and approximate AUC with the hinge loss function, and derive convex reformulations using duality. The DR-AUC models outperform deterministic AUC and support vector machine models and have superior worst-case out-of-sample performance, thereby showing their robustness. The results are encouraging since the numerical experiments are conducted with small-size training sets conducive to low out-of-sample performance.     

A numerical algorithm for computing tsunami wave amplitudes

A numerical multistep algorithm for computing tsunami wave front amplitudes is proposed. The first step consists in solving an appropriate eikonal equation. The eikonal equation is solved with Godunov’s approach and a bicharacteristic method. A qualitative comparison of the two methods is done. A change of variables is made with the eikonal equation solution at the second step. At the last step, using an expansion of the fundamental solution to the shallow water equations in the new variables, we obtain a Cauchy problem of lesser dimension for the leading edge wave amplitude. The results of numerical experiments are presented.     

Attractive force search algorithm for piecewise convex maximization problems

We consider mathematical programming problems with the so-called piecewise convex objective functions. A solution method for this interesting and important class of nonconvex problems is presented. This method is based on Newton??s law of universal gravitation, multicriteria optimization and Helly??s theorem on convex bodies. Numerical experiments using well known classes of test problems on piecewise convex maximization, convex maximization as well as the maximum clique problem show the efficiency of the approach.     

A numerical algorithm for simulation of the Q-switched fiber laser using the travelling wave model

We develop a finite-difference scheme for approximation of a system of nonlinear PDEs describing the Q-switching process. We construct it by using staggered grids. The transport equations are approximated along characteristics, and quadratic nonlinear functions are linearized using a special selection of staggered grids. The stability analysis proves that a connection between time and space steps arises only due to approximation requirements in order to follow exactly the directions of characteristics. The convergence analysis of this scheme is done in two steps. First, some estimates of the uniform boundedness of the discrete solution are proved. This part of the analysis is done locally, in some neighborhood of the exact solution. Second, on the basis of the obtained estimates, the main stability inequality is proved. The second-order convergence rate with respect to the space and time coordinates follows from this stability estimate. Using the obtained convergence result, we prove that the local stability analysis in the selected neighborhood of the exact solution is sufficient.     

Improved variational image registration model and a fast algorithm for its numerical approximation

In a multimodal image registration scenario, where two given images have similar features, but noncomparable intensity variations, the sum of squared differences is not suitable for inferring image similarities. In this article, we first propose a new variational model based on combining intensity and geometric transformations, as an alternative to use mutual information and an improvement to the work by Modersitzki and Wirtz (Modersitzki and Wirtz, Lect Notes Comput Sci 4057 (2006), 257–263), and then develop a fast multigrid (MG) algorithm for solving the underlying system of fourth‐order and nonlinear partial differential equations. We can demonstrate the effective smoothing property of the adopted primal‐dual smoother by a local Fourier analysis. Numerical tests will be presented to show both the improvements achieved in image registration quality and MG efficiency. © 2011 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2011     

A numerical algorithm for the nonlinear Timoshenko beam system

An initial boundary value problem is considered for the dynamic beam system Its solution is found by means of an algorithm, the constituent parts of which are the finite element method, the implicit symmetric difference scheme used to approximate the solution with respect to the spatial and time variables, and also a Picard type iteration process for solving the system of nonlinear equations obtained by discretization. Errors of three parts of the algorithm are estimated and, as a result, its total error estimate is obtained. A numerical example is solved.     

A numerical algorithm for the nonlinear Kirchhoff string equation

The initial boundary value problem is considered for the dynamic string equation . Its solution is found by means of an algorithm, the constituent parts of which are the Galerkin method, the modified Crank-Nicolson difference scheme used to perform approximation with respect to spatial and time variables, and also a Picard type iteration process for solving the system of nonlinear equations obtained by discretization. Errors of the three parts of the algorithm are estimated and, as a result, its total error estimate is obtained.     

A numerical algorithm for nonlinear multi-point boundary value problems

In this paper, an algorithm is presented for solving second-order nonlinear multi-point boundary value problems (BVPs). The method is based on an iterative technique and the reproducing kernel method (RKM). Two numerical examples are provided to show the reliability and efficiency of the present method.     

A numerical algorithm for singular optimal LQ control systems

A numerical algorithm to obtain the consistent conditions satisfied by singular arcs for singular linear–quadratic optimal control problems is presented. The algorithm is based on the Presymplectic Constraint Algorithm (PCA) by Gotay-Nester (Gotay et al., J Math Phys 19:2388–2399, 1978; Volckaert and Aeyels 1999) that allows to solve presymplectic Hamiltonian systems and that provides a geometrical framework to the Dirac-Bergmann theory of constraints for singular Lagrangian systems (Dirac, Can J Math 2:129–148, 1950). The numerical implementation of the algorithm is based on the singular value decomposition that, on each step, allows to construct a semi-explicit system. Several examples and experiments are discussed, among them a family of arbitrary large singular LQ systems with index 2 and a family of examples of arbitrary large index, all of them exhibiting stable behaviour. Research partially supported by MEC grant MTM2004-07090-C03-03. SIMUMAT-CM, UC3M-MTM-05-028 and CCG06-UC3M/ESP-0850.     

A numerical algorithm for the solution of Signorini problems

In this paper we propose a new iterative algorithm for the solution of a certain class of Signorini problems. Such problems arise in the modelling of a variety of physical phenomena and usually involve the determination of an unknown free boundary. Here we describe a way of locating the free boundary directly and provide a proof that the algorithm converges when used with analytic methods. The advantage of this algorithm is that it can be used in conjunction with any numerical method with minimal development of extra code. We demonstrate its application with the boundary element method to some physical problems in both two and three dimensions.     

A Bayesian network model for spatial event surveillance

Methods for spatial cluster detection attempt to locate spatial subregions of some larger region where the count of some occurrences is higher than expected. Event surveillance consists of monitoring a region in order to detect emerging patterns that are indicative of some event of interest. In spatial event surveillance, we search for emerging patterns in spatial subregions.A well-known method for spatial cluster detection is Kulldorff’s [M. Kulldorff, A spatial scan statistic, Communications in Statistics: Theory and Methods 26 (6) (1997)] spatial scan statistic, which directly analyzes the counts of occurrences in the subregions. Neill et al. [D.B. Neill, A.W. Moore, G.F. Cooper, A Bayesian spatial scan statistic, Advances in Neural Information Processing Systems (NIPS) 18 (2005)] developed a Bayesian spatial scan statistic called BSS, which also directly analyzes the counts.We developed a new Bayesian-network-based spatial scan statistic, called BNetScan, which models the relationships among the events of interest and the observable events using a Bayesian network. BNetScan is an entity-based Bayesian network that models the underlying state and observable variables for each individual in a population.We compared the performance of BNetScan to Kulldorff’s spatial scan statistic and BSS using simulated outbreaks of influenza and cryptosporidiosis injected into real Emergency Department data from Allegheny County, Pennsylvania. It is an open question whether we can obtain acceptable results using a Bayesian network if the probability distributions in the network do not closely reflect reality, and thus, we examined the robustness of BNetScan relative to the probability distributions used to generate the data in the experiments. Our results indicate that BNetScan outperforms the other methods and its performance is robust relative to the probability distribution that is used to generate the data.