Search

This study deals with a narrow escape problem, a well-know difficult problem of evaluating the probability for a diffusing particle to reach a small part of a boundary far away from the starting position of the particle. A direct simulation of the diffusion trajectories would take an enormous computer simulation time. Instead, we use a different approach which drastically improves the efficiency of the diffusion trajectory tracking algorithm by introducing an artificial drift velocity directed to the target position. The method can be efficiently applied to solve narrow escape problems for domains of long extension in one direction which is the case in many practical problems in biology and chemistry. The algorithm is meshless both in space and time, and is well applied to solve high-dimensional problems in complicated domains. We present in this paper a detailed numerical analysis of the method for the case of a rectangular parallelepiped. Both stationary and transient diffusion problems are handled. [ABSTRACT FROM AUTHOR]

In this paper we consider the branched transportation problem in two dimensions associated with a cost per unit length of the form 1 + β ⁢ θ {1+\beta\,\theta} , where θ denotes the amount of transported mass and β > 0 {\beta>0} is a fixed parameter (notice that the limit case β = 0 {\beta=0} corresponds to the classical Steiner problem). Motivated by the numerical approximation of this problem, we introduce a family of functionals ( { ℱ ε } ε > 0 {\{\mathcal{F}_{\varepsilon}\}_{\varepsilon>0}}) which approximate the above branched transport energy. We justify rigorously the approximation by establishing the equicoercivity and the Γ-convergence of { ℱ ε } {\{\mathcal{F}_{\varepsilon}\}} as ε ↓ 0 {\varepsilon\downarrow 0}. Our functionals are modeled on the Ambrosio–Tortorelli functional and are easy to optimize in practice. We present numerical evidences of the efficiency of the method. [ABSTRACT FROM AUTHOR]

Total variation (TV) based models have been used widely in multiplicative denoising problem. However, these models are always accompanied by an unsatisfactory effect named staircase due to the property of BV space. In this paper, we present two high-order variational models based on total generalized variation (TGV) for two kinds of multiplicative noises. The proposed models reduce the staircase while preserving the edges. In the meantime we develop an efficient algorithm which is called Prediction-Correction proximal alternative direction method of multipliers (PADMM) to solve our models. Moreover, we show the convergence of our algorithm under certain conditions. Numerical experiments demonstrate that our high-order models outperform the classical TV-based models in PSNR and SSIM values. [ABSTRACT FROM AUTHOR]

The ziggurat method is a fast random variable generation method introduced by Marsaglia and Tsang in a series of papers. We discuss how the ziggurat method can be implemented for low-discrepancy sequences, and present algorithms and numerical results when the method is used to generate samples from the normal and gamma distributions. [ABSTRACT FROM AUTHOR]

The block inverse iteration and block Newton’s methods proposed by the authors of this paper for computing invariant pairs of regular linear matrix pencils are generalized to the case of regular nonlinear matrix pencils. Numerical properties of the proposed methods are demonstrated with a typical quadratic eigenproblem. [ABSTRACT FROM AUTHOR]

A new combined numerical algorithm for solving inverse problems of epidemiology is described in this paper. The combined algorithm consists of optimization and iterative methods, and determines the parameters specific to a particular population by using the statistical information for a few previous years. The coefficients of the epidemiology model describe particular qualities of the population and the development of the disease. The inverse problem of parameter identification in a mathematical model is reduced to the problem of minimizing an objective function characterizing the square deviation of the statistical data from the experimental data. The combination of statistical and optimization algorithms demonstrates the identification of parameters with an appropriate relative accuracy of 30%. The results can be used by public health organizations to predict the infectious disease epidemic in a given region by comparing the data of simulation with historical data. [ABSTRACT FROM AUTHOR]

Matsumoto, Saito and Matoba recently proposed the Walsh figure of merit (WAFOM), which is a computable criterion for quasi-Monte Carlo point sets using digital nets. Several algorithms have been proposed for finding low-WAFOM point sets. In the existing algorithms, the number of points is fixed in advance, but extensible point sets are preferred in some applications. In this paper, we propose a random search algorithm for extensible low-WAFOM point sets. For this, we introduce a method that uses lookup tables to compute WAFOM faster. Numerical results show that our extensible low-WAFOM point sets are comparable with Niederreiter-Xing sequences for some low-dimensional and smooth test functions. [ABSTRACT FROM AUTHOR]

A newmethod solving the initial data assimilation problemis proposed in the paper. Themethod is based on the results of the theory of global attractors. The numerical algorithmis formulated, its convergence is justified, analysis of computational formulas is performed. It is shown that themethod is equivalent in some sense to the construction of nontrivial trajectories of a global attractor and also to solving the stabilization problem in terms of projections onto an unstable manifold. This result allows us to consolidate the theory of iterative methods for stabilization to unstable trajectories of the hyperbolic type based on the properties of local invariant stable and unstable manifolds. [ABSTRACT FROM AUTHOR]

The generation of appropriate parallel and high-quality quasirandom sequences (low-discrepancy sequences) is crucial to the success of quasi-Monte Carlo methods. The Kronecker sequence is well known to be one of the special types of low-discrepancy sequences, and one of its important advantages is that the Kronecker sequence is easy to implement due to its definition via the fractional parts of multiples of irrationals. However, the original Kronecker sequence suffers from correlations for different dimensions. These correlations result in poorly distributed two-dimensional projections. An approach to this is to find a modified Kronecker sequence via generalizing golden ratio and generate parallel sequences. This paper presents a new algorithm for finding a modified Kronecker sequence within special choices of irrationals. This modified sequence is numerically tested and shown empirically to be superior to the other widely used quasirandom sequences. In addition, based on analysis and insight into the correlations between dimensions of the Kronecker sequence, we illustrate why our algorithm is efficient for breaking these correlations. [ABSTRACT FROM AUTHOR]

This is a review paper of the role of Carleman estimates in the theory of multidimensional coefficient inverse problems since the first inception of this idea in 1981. [ABSTRACT FROM AUTHOR]

The connection between exponential sums and algebraic varieties has been known for at least six decades. Recently, Lisoněk exploited it to reformulate the Charpin-Gong characterization of a large class of hyper-bent functions in terms of numbers of points on hyperelliptic curves. As a consequence, he obtained a polynomial time and space algorithm for certain subclasses of functions in the Charpin-Gong family. In this paper, we settle a more general framework, together with detailed proofs, for such an approach and show that it applies naturally to a distinct family of functions proposed by Mesnager. Doing so, a polynomial time and space test for the hyper-bentness of functions in this family is obtained as well. Nonetheless, a straightforward application of such results does not provide a satisfactory criterion for explicit generation of functions in the Mesnager family. To address this issue, we show how to obtain a more efficient test leading to a substantial practical gain. We finally elaborate on an open problem about hyperelliptic curves related to a family of Boolean functions studied by Charpin and Gong. [ABSTRACT FROM AUTHOR]

Algorithms of the 'method of similar trajectories' (MST) are implemented by a numerical-statistical simulation of the trajectories of particles, which are radiation 'quanta', according to an auxiliary radiation model and construction of weighted estimates of the functionals simultaneously for different values of 'physical' parameters. This paper is focused on the theoretical and numerical solution of the problem of choosing this auxiliary model with the aim to minimize the parametric maximum of the mean-square error of weighted estimates. We formulate new assertions concerning minimax MST algorithms and refine some previously known statements. [ABSTRACT FROM AUTHOR]

The work is focused on the study of the tsunami source reconstruction problem based on the wave level observations. The problem within the linear shallow water model and the 'piston' model of tsunami wave generation is considered. This problem relates to the class of incorrectly posed problems, its study is based on the general approach described in [2]. In this paper a theorem on the solvability of the problem is proved and the results of numerical experiments for the Pacific Ocean confirming the efficiency of the proposed solution algorithms are presented. [ABSTRACT FROM AUTHOR]

In this paper, we combine concepts from two different mathematical research topics: adaptive wavelet techniques for well-posed problems and regularization theory for nonlinear inverse problems with sparsity constraints. We are concerned with identifying certain parameters in a parabolic reaction-diffusion equation from measured data. Analytical properties of the related parameter-to-state operator are summarized, which justify the application of an iterated soft shrinkage algorithm for minimizing a Tikhonov functional with sparsity constraints. The forward problem is treated by means of a new adaptive wavelet algorithm which is based on tensor wavelets. In its general form, the underlying PDE describes gene concentrations in embryos at an early state of development. We implemented an algorithm for the related nonlinear parameter identification problem and numerical results are presented for a simplified test equation. [ABSTRACT FROM AUTHOR]

In this paper, we describe a stochastic algorithm to solve sudoku puzzles. Our method consists in computing probabilities for each symbol of each cell updated at each step of the algorithm using estimation of distributions algorithms (EDA). This update is done using the empirical estimators of these probabilities for a fraction of the best puzzles according to a cost function. We develop also some partial restart techniques in the RESEDA algorithm to obtain a convergence for the most difficult puzzles. Our algorithm is tested numerically on puzzles with various levels of difficulty starting from very easy ones to very hard ones including the famous puzzle AI Escargot. The CPU times vary from few hundreds of a second for the easy ones to about one minute for the most difficult one. [ABSTRACT FROM AUTHOR]

This paper is focused on the development of numerical algorithms based on the natural element method for the solution of problems of incompressible fluid dynamics with free boundaries. [ABSTRACT FROM AUTHOR]

In this paper we study the average complexity of optimal algorithms solving the problem of searching for identical objects (PSIO) for random databases. We describe and investigate classes of PSIOs for which the average complexity as a function of the database volume grows logarithmically. For such classes of problems we find exact asymptotics of the complexity. We also study the case where the complexity of the optimal algorithm averaged over the class of problems is bounded and construct a class of PSIOs such that the average complexity of the optimal algorithm is an unbounded function growing slower than the logarithm. [ABSTRACT FROM AUTHOR]

In elliptic curve cryptosystems, scalar multiplications performed on the curves have much effect on the efficiency of the schemes, and many efficient methods have been proposed. In particular, recoding methods of the scalars play an important role in the performance of the algorithm used. For integer radices, the non-adjacent form (NAF) and its generalizations (e.g., the generalized non-adjacent form (GNAF) and the radix- r non-adjacent form ( rNAF)) have been proposed for minimizing the non-zero densities in the representations of the scalars. On the other hand, for subfield elliptic curves, the Frobenius expansions of the scalars can be used for improving efficiency. Unfortunately, there are only a few methods apply the techniques of NAF or its analogue to the Frobenius expansion, namely τ-adic NAF techniques on Koblitz curves and hyperelliptic Koblitz curves. In this paper, we try to combine these techniques, namely recoding methods for reducing non-zero density and the Frobenius expansion, and propose two new efficient recoding methods of scalars on more general family of subfield elliptic curves in odd characteristic. We also prove that the non-zero densities for the new methods are same as those for the original GNAF and rNAF. We estimate scalar multiplication costs on the above subfield elliptic curves in terms of elliptic curve operations and finite field operations for several previous methods and the proposed methods. In addition, we implement scalar multiplication on an subfield elliptic curve belonging to the above family, for the previous methods and a proposed method. As a result, our estimation and implementation show that the speed of the proposed methods improve between 8% and 50% over that for the Frobenius expansion method. [ABSTRACT FROM AUTHOR]

In this paper, the possibility of using the reverse connection control for iteratively regularized Gauss–Newton-type algorithms is analyzed. It is shown that for the generalized Gauss–Newton iterations the diameter of the set containing the control elements can tend to ∞ as n → ∞. To further improve the stabilizing properties of the Gauss–Newton scheme, a new penalty term is proposed that can depend nonlinearly on the current iteration. As a test numerical example, a nonlinear inverse scattering problem of computing a 2D obstacle shape is considered. [ABSTRACT FROM AUTHOR]

Implicit finite difference schemes of approximate factorization and predictor-corrector schemes based on special operator splitting are proposed in this paper for numerical solution of Navier–Stokes equations for a compressible heat-conducting gas. These schemes are implemented by scalar sweep methods and are unconditionally stable. The calculations of complicated twodimensional flows performed here confirm the sufficient accuracy of the proposed algorithms and their efficiency. [ABSTRACT FROM AUTHOR]

In the paper we present several numerical algorithms to simulate the fractional Brownian motion (the generalized Wiener process). The algorithms have been developed on the basis of the integral representation of the fractional Brownian motion and the spectral decomposition for its increments. The convergence of the numerical methods has been studied. [ABSTRACT FROM AUTHOR]

This paper presents a numerical method for aerodynamic shape optimization problems with state constraint. It uses a simultaneous semi-iterative technique to solve the equations arising from the first order necessary optimality conditions. Although there is no theoretical proof of convergence of this algorithm so far, in our numerical experiments the method converges without additional globalization in the design space. A reduced SQP method based preconditioner is used for convergence acceleration. Design examples of drag reduction with constant lift for wing and body of a Supersonic Commercial Transport (SCT) aircraft are included. The overall cost of computation is about 8 forward simulation runs. [ABSTRACT FROM AUTHOR]

Two methods for analysing stochastic control systems with distributed changes of structures are considered: statistical simulation and the spectral method. Algorithms for solving the problem are presented in the paper. The comparison of the methods and their efficiency are demonstrated on model problems. [ABSTRACT FROM AUTHOR]

In this paper we propose a numerical method for solving nonstationary Maxwell equations on unstructured triangular grids, which is based on the finite volume method. We give the results of test calculations which confirm the second order of convergence of the method both for homogeneous media and media with space-variable dielectric permittivity. [ABSTRACT FROM AUTHOR]

In this paper we describe results obtained in numerical investigation of the mechanism of tsunami generation by a moving submerged landslide which is simulated by a solid body sliding down a slope. The authors perform complex multiparameter calculations by algorithms based on the hierarchy of wave hydrodynamics models comprising shallow water equations and full hydrodynamical equations of an ideal fluid. We investigate the crucial dependences of the wave formation process on the length and thickness of the landslide, its bedding depth, and the law of motion. A comparison of solutions obtained by the approximate and full models allowed us to assess the degree of impact of the vertical flow structure and specify the domain of applicability of the approximate models. [ABSTRACT FROM AUTHOR]

In this paper, a boundary integral method is used to solve an inverse heat conduction problem. An algorithm for the inverse problem of the one dimensional case is given by using the fundamental solution. Numerical results show that our algorithm is effective. [ABSTRACT FROM AUTHOR]

The present paper discusses the results of the numerical simulation of the process of surface wave generation by a moving underwater landslide. The computational algorithms are based on finite difference schemes for shallow water equations of different orders of hydrodynamic approximation and equations for potential ideal fluid flows with a free boundary. The dependence of the parameters of generated waves on the law of motion of the migrating bottom fragment is studied. [ABSTRACT FROM AUTHOR]

An algorithm for the simultaneous determination of two coefficients in an inverse problem for equations of the parabolic type is studied. The model under investigation has been proposed by H. de Vriend and M. Capobianco to describe the long-time coastal profile evolution. The iterative inversion procedure is based on the minimization of a suitable cost functional. Results of numerical tests are shown to illustrate the performance of the algorithm. The real measured data of the coastal profile evolution have been numerically processed to validate the aforementioned diffusion type model. The paper is targetly oriented to attract attention of professionals, who study Inverse Problems, to such new area of applications as Coastal Engineering. [ABSTRACT FROM AUTHOR]

In the paper we numerically solve an inverse problem of determination of medium parameters of a member of thin anisotropic layers for an elasticity system. We also investigate a case of a transversely isotropic medium with the symmetry axis lying in the plane Oxy. For example, this model can describe a vertically fractured medium. We present one of the possible ways of numerical solution of the problem. Examples of the numerical reconstruction show efficiency of the algorithm offered. [ABSTRACT FROM AUTHOR]

In this paper it is shown that the fast multigrid algorithm (FMA) first proposed by the author in [1] is applicable to the solution of a sufficiently broad family of quasisingulsar classes of diffusion problems. The optimal accuracy in the sense of the Kolmogorov N-width is attained using O(|ln ε|3N) operations, where ε is the minimum value of the coefficient in the problem. [ABSTRACT FROM AUTHOR]

In this paper we propose an improved quasi-Monte Carlo method for solving Linear Algebra problems. We show that by using low-discrepancy sequences both the convergence and the CPU time of the algorithm are improved. Two parallelization schemes using the Message Passing Interface with static and dynamic load balancing are proposed. The dynamic scheme is useful for computing in the GRID environment. [ABSTRACT FROM AUTHOR]

In this paper, we investigate the method of the numerical solution of boundary value problems in inhomogeneous domains composed of homogeneous multidimensional parallelepipeds. The method is the symbiosis of high-order difference schemes in homogeneous subdomains and multipoint one-dimensional boundary conditions at interfaces. Due to splitting, the boundary value problem reduces to systems of linear algebraic equations with matrices different from a tridiagonal matrix by the availability of separate 'long' rows with more than three nonzero elements. Two algorithms are investigated to solve these systems. The first algorithm is based on the immediate transformation of the system of equations to a tridiagonal form. The second one is a generalization of the known sweep parallelizing method. [ABSTRACT FROM AUTHOR]

In this paper we propose an iterative algorithm for the solution of Volterra equations of the first kind whose kernel is a square matrix. The algorithm, essential the Lavrientev method coupled with discretization, is "direct in the sense that preliminary numerical computation of the derivative of the observed variable is not required. We assume boundedness of the input μ and mild regularity conditions of the kernel. We prove convergence of the algorithm in L[supP] (0,T), 1 ≤ p < +∞ and uniform convergence on the intervals where the input is continuous. Under additional information on μ we give both integral and pointwise convergence estimates. The observed variable is read with errors, at discrete time instants. [ABSTRACT FROM AUTHOR]