A Low-Memory Algorithm for Point Counting on Picard Curves

Combining the ideas of Bauer, Teske and Weng, [1] and Gaudry, Schost [3], we give a low memory algorithm for computing the number of points on the Jacobian of a Picard curve. It is efficient enough to handle Picard curves over finite prime fields , where p is a prime with 58 bits. We present an example where the Jacobian has a prime group order of size 2¹⁷⁴     

Partitioned quasi-Newton methods for sparse nonlinear equations

In this paper, we present two partitioned quasi-Newton methods for solving partially separable nonlinear equations. When the Jacobian is not available, we propose a partitioned Broyden’s rank one method and show that the full step partitioned Broyden’s rank one method is locally and superlinearly convergent. By using a well-defined derivative-free line search, we globalize the method and establish its global and superlinear convergence. In the case where the Jacobian is available, we propose a partitioned adjoint Broyden method and show its global and superlinear convergence. We also present some preliminary numerical results. The results show that the two partitioned quasi-Newton methods are effective and competitive for solving large-scale partially separable nonlinear equations.     

Computing reachable sets for uncertain nonlinear monotone systems

We address nonlinear reachability computation for uncertain monotone systems, those for which flows preserve a suitable partial orderings on initial conditions. In a previous work Ramdani (2008) [22], we introduced a nonlinear hybridization approach to nonlinear continuous reachability computation. By analysing the signs of off-diagonal elements of system’s Jacobian matrix, a hybrid automaton can be obtained, which yields component-wise bounds for the reachable sets. One shortcoming of the method is induced by the need to use whole sets for addressing mode switching. In this paper, we improve this method and show that for the broad class of monotone dynamical systems, component-wise bounds can be obtained for the reachable set in a separate manner. As a consequence, mode switching no longer needs to use whole solution sets. We give examples which show the potentials of the new approach.     

无界区域上基于自然边界归化的一种区域分解算法

无界区域上基于自然边界归化的一种区域分解算法余德浩（中国科学院计算中心）ＡＤＯＭＡＩＮＤＥＣＯＭＰＯＳＩＴＩＯＮＭＥＴＨＯＤＢＡＳＥＤＯＮＴＨＥＮＡＴＵＲＡＬＢＯＵＮＤＡＲＹＲＥＤＵＣＴＩＯＮＯＶＥＲＵＮＢＯＵＮＤＥＤＤＯＭＡＩＮ￥ＹｕＤｅ－ｈａｏ（...     

Some computational aspects of Jacobians of curves in the family y3=γx5+δ over Fp

In this paper, we study the Jacobian varieties of certain diagonal curves of genus four: we first give the structure of the Jacobian, showing that it is simple over the prime field in most cases, then we give a reduction algorithm, suitable for calculations in the group of its rational points.     

A reliable treatment of Abel’s second kind singular integral equations

The central idea of this paper is to construct a new mechanism for the solution of Abel’s type singular integral equations that is to say the two-step Laplace decomposition algorithm. The two-step Laplace decomposition algorithm (TSLDA) is an innovative adjustment in the Laplace decomposition algorithm (LDA) and makes the calculation much simpler. In this piece of writing, we merge the Laplace transform and decomposition method and present a novel move toward solving Abel’s singular integral equations.     

Newton’s method for computing a normalized equilibrium in the generalized Nash game through fixed point formulation

We consider the generalized Nash equilibrium problem (GNEP), where not only the players’ cost functions but also their strategy spaces depend on the rivals’ decision variables. Existence results for GNEPs are typically shown by using a fixed point argument for a certain set-valued function. Here we use a regularization of this set-valued function in order to obtain a single-valued function that is easier to deal with from a numerical point of view. We show that the fixed points of the latter function constitute an important subclass of the generalized equilibria called normalized equilibria. This fixed point formulation is then used to develop a nonsmooth Newton method for computing a normalized equilibrium. The method uses a so-called computable generalized Jacobian that is much easier to compute than Clarke generalized Jacobian or B-subdifferential. We establish local superlinear/quadratic convergence of the method under the constant rank constraint qualification, which is weaker than the frequently used linear independence constraint qualification, and a suitable second-order condition. Some numerical results are presented to illustrate the performance of the method.     

Nonsingularity of FB system and constraint nondegeneracy in semidefinite programming

For a KKT point of the linear semidefinite programming (SDP), we show that the nonsingularity of the B-subdifferential of Fischer-Burmeister (FB) nonsmooth system, the nonsingularity of Clarke’s Jacobian of this system, and the primal and dual constraint nondegeneracies, are all equivalent. Also, each of these conditions is equivalent to the nonsingularity of Clarke’s Jacobian of the smoothed counterpart of FB nonsmooth system, which particularly implies that the FB smoothing Newton method may attain the local quadratic convergence without strict complementarity assumption. We also report numerical results of the FB smoothing method for some benchmark problems.     

Modified variational iteration method for solving Fisher’s equations

In this paper, we apply the modified variational iteration method (MVIM) for solving Fisher’s equations. The proposed modification is made by introducing He’s polynomials in the correction functional. The suggested algorithm is quite efficient and is practically well suited for use in these problems. The proposed iterative scheme finds the solution without any discretization, linearization or restrictive assumptions. Several examples are given to verify the reliability and efficiency of the method. The fact that the proposed technique solves nonlinear problems without using Adomian’s polynomials can be considered as a clear advantage of this algorithm over the decomposition method.     

New solution approaches for the maximum-reliability stochastic network interdiction problem

We investigate methods to solve the maximum-reliability stochastic network interdiction problem (SNIP). In this problem, a defender interdicts arcs on a directed graph to minimize an attacker’s probability of undetected traversal through the network. The attacker’s origin and destination are unknown to the defender and assumed to be random. SNIP can be formulated as a stochastic mixed-integer program via a deterministic equivalent formulation (DEF). As the size of this DEF makes it impractical for solving large instances, current approaches to solving SNIP rely on modifications of Benders decomposition. We present two new approaches to solve SNIP. First, we introduce a new DEF that is significantly more compact than the standard DEF. Second, we propose a new path-based formulation of SNIP. The number of constraints required to define this formulation grows exponentially with the size of the network, but the model can be solved via delayed constraint generation. We present valid inequalities for this path-based formulation which are dependent on the structure of the interdicted arc probabilities. We propose a branch-and-cut (BC) algorithm to solve this new SNIP formulation. Computational results demonstrate that directly solving the more compact SNIP formulation and this BC algorithm both provide an improvement over a state-of-the-art implementation of Benders decomposition for this problem.     

Solution of twelfth-order boundary value problems by variational iteration technique

In this paper, we implement a relatively new analytical technique which is called the variational iteration method for solving the twelfth-order boundary value problems. The analytical results of the problems have been obtained in terms of convergent series with easily computable components. Comparisons are made to verify the reliability and accuracy of the proposed algorithm. Several examples are given to check the efficiency of the suggested technique. The fact that variational iteration method solves nonlinear problems without using the Adomian’s polynomials is a clear advantage of this technique over the decomposition method.     

A nonmonotone Jacobian smoothing inexact Newton method for NCP

In this paper we propose Jacobian smoothing inexact Newton method for nonlinear complementarity problems (NCP) with derivative-free nonmonotone line search. This nonmonotone line search technique ensures globalization and is a combination of Grippo-Lampariello-Lucidi (GLL) and Li-Fukushima (LF) strategies, with the aim to take into account their advantages. The method is based on very well known Fischer-Burmeister reformulation of NCP and its smoothing Kanzow’s approximation. The mixed Newton equation, which combines the semismooth function with the Jacobian of its smooth operator, is solved approximately in every iteration, so the method belongs to the class of Jacobian smoothing inexact Newton methods. The inexact search direction is not in general a descent direction and this is the reason why nonmonotone scheme is used for globalization. Global convergence and local superlinear convergence of method are proved. Numerical performances are also analyzed and point out that high level of nonmonotonicity of this line search rule enables robust and efficient method.     

Modified variational iteration method for solving fourth-order boundary value problems

In this paper, we apply the modified variational iteration method (MVIM) for solving the fourth-order boundary value problems. The proposed modification is made by introducing He’s polynomials in the correction functional. The suggested algorithm is quite efficient and is practically well suited for use in these problems. The proposed iterative scheme finds the solution without any discretization, linearization or restrictive assumptions. Several examples are given to verify the reliability and efficiency of the method. The fact that the proposed technique solves nonlinear problems without using the Adomian’s polynomials can be considered as a clear advantage of this algorithm over the decomposition method.     

An efficient computational approach for multiframe blind deconvolution

Obtaining high resolution images of space objects from ground based telescopes involves using a combination of sophisticated hardware and computational post-processing techniques. An important, and often highly effective, computational post processing tool is multiframe blind deconvolution (MFBD). Mathematically, MFBD is modeled as a nonlinear inverse problem that can be solved using a flexible, variable projection optimization approach. In this paper we consider MFBD problems that are parameterized by a large number of variables. The formulas required for efficient implementation are carefully derived using the spectral decomposition and by exploiting properties of conjugate symmetric vectors. In addition, a new approach is proposed to provide a mathematical decoupling of the optimization problem, leading to a block structure of the Jacobian matrix. An application in astronomical imaging is considered, and numerical experiments illustrate the effectiveness of our approach.     

An Inexact PRP Conjugate Gradient Method for Symmetric Nonlinear Equations

In this article, without computing exact gradient and Jacobian, we proposed a derivative-free Polak-Ribière-Polyak (PRP) method for solving nonlinear equations whose Jacobian is symmetric. This method is a generalization of the classical PRP method for unconstrained optimization problems. By utilizing the symmetric structure of the system sufficiently, we prove global convergence of the proposed method with some backtracking type line search under suitable assumptions. Moreover, we extend the proposed method to nonsmooth equations by adopting the smoothing technique. We also report some numerical results to show its efficiency.     

On a trust region method without exact Jacobian matrices

Automatic differentiation (AD) provides a possibility to evaluate exact derivative information within working accuracy. Here, we present an approach for equality constrained optimization that is based essentially on AD by computing only direct sensitivities and adjoints of first and second order. Employing this information, we generate approximations of the required derivative matrices using the STR1 update instead of computing the full constraint Jacobian or the full Lagrangian Hessian at each iteration explicitly. Hence, this approach avoids the forming and factoring of the exact constraint Jacobian that is often required in each iteration step. In order to globalize this provable local convergent method, the algorithm was embedded in a trust-region framework. We apply a composite-step method similar to the Byrd-Omojokun approach that is well suited for the available information from the approximated matrices. For that purpose, the normal step is given by the dogleg method whereas a generalized CG-iteration is applied to compute the tangential step. Here, the fact that only inexact information of the constraint Jacobian is available forms the main difference to other existing algorithms, where often a factorization of the exact Jacobian is used. Numerical results are shown for an equality constrained problem of the CUTE set and a PDE-based optimization problem. (© 2005 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Matrix-free monolithic homotopy continuation with application to computational aerodynamics

A matrix-free monolithic homotopy continuation algorithm is developed which allows for approximate numerical solutions to nonlinear systems of equations without the need to solve a linear system, thereby avoiding the formation of any Jacobian or preconditioner matrices. The algorithm can converge from an arbitrary starting guess, under suitable conditions, and can give a sufficiently accurate approximation to the converged solution such that a rapid locally convergent method such as Newton’s method will converge successfully. Several forms of the algorithm are presented, as are augmentations to the algorithms which can lead to improved efficiency or stability. The method is validated and the stability and efficiency are investigated numerically based on a computational aerodynamics flow solver.     

Local convergence of an adaptive scalar method and its application in a nonoverlapping domain decomposition scheme

In this paper, we demonstrate a local convergence of an adaptive scalar solver which is practical for strongly diagonal dominant Jacobian problems such as in some systems of nonlinear equations arising from the application of a nonoverlapping domain decomposition method. The method is tested to a nonlinear interface problem of a multichip heat conduction problem. The numerical results show that the method performs slightly better than a Newton-Krylov method.     

Contour integral method for European options with jumps

We develop an efficient method for pricing European options with jump on a single asset. Our approach is based on the combination of two powerful numerical methods, the spectral domain decomposition method and the Laplace transform method. The domain decomposition method divides the original domain into sub-domains where the solution is approximated by using piecewise high order rational interpolants on a Chebyshev grid points. This set of points are suitable for the approximation of the convolution integral using Gauss–Legendre quadrature method. The resulting discrete problem is solved by the numerical inverse Laplace transform using the Bromwich contour integral approach. Through rigorous error analysis, we determine the optimal contour on which the integral is evaluated. The numerical results obtained are compared with those obtained from conventional methods such as Crank–Nicholson and finite difference. The new approach exhibits spectrally accurate results for the evaluation of options and associated Greeks. The proposed method is very efficient in the sense that we can achieve higher order accuracy on a coarse grid, whereas traditional methods would required significantly more time-steps and large number of grid points.     

Improved Newton’s method without direct function evaluations

For solving systems of nonlinear equations, we have recently developed a Newton’s method to manage issues with inaccurate function values or problems with high computational cost. In this work we introduce a modification of the above method, reducing the total computational cost and improving, in general, its overall performance. Moreover, the proposed version retains the quadratic convergence, the good behavior over singular and ill-conditioned cases of Jacobian matrix, and its capability to be ideal for imprecise function problems. Numerical results demonstrate the efficiency of the new proposed method.