A technique to choose the most efficient method between secant method and some variants

A few variants of the secant method for solving nonlinear equations are analyzed and studied. In order to compute the local order of convergence of these iterative methods a development of the inverse operator of the first order divided differences of a function of several variables in two points is presented using a direct symbolic computation. The computational efficiency and the approximated computational order of convergence are introduced and computed choosing the most efficient method among the presented ones. Furthermore, we give a technique in order to estimate the computational cost of any iterative method, and this measure allows us to choose the most efficient among them.     

A fast multiscale solver for modified Hammerstein equations

This paper presents a fast solver, called the multilevel augmentation method, for modified nonlinear Hammerstein equations. When we utilize the method to solve a large scale problem, most of components of the solution can be computed directly, and lower frequency components can be obtained by solving a fixed low-order algebraic nonlinear system. The advantage of using the algorithm to modified equations is that it leads to reduce the cost of numerical integrations greatly. The optimal error estimate of the method is established and the nearly linear computational complexity is proved. Finally, numerical examples are presented to confirm the theoretical results and illustrate the efficiency of the method.     

On the one problem of wave diagnostic

This work is devoted to the development of methods and algorithms of the solution of a nonlinear three-dimensional inverse problem of wave diagnostics of heterogeneities in homogeneous environments in approximation of Helmholtz equation. By virtue of computational complexity of the problem, its solution is possible only with use of a supercomputer. The problem consists in seeking the unknown factor in the equation with partial derivatives. The problem is transformed to a system of operator equations with respect to an unknown factor and a wave field. Effective algorithms of its solution with the use of supercomputers having a parallel architecture as a result.     

Space-Time Meshfree Collocation Method for PDEs

An innovative Space-Time Meshfree Collocation Method (STMCM) for solving systems of nonlinear ordinary and partial differential equations by a consistent discretization in both space and time is proposed as an alternative to established mesh-based methods. The STMCM belongs to the class of truly meshfree methods, i.e. the methods which do not have any underlying mesh, but work on a set of nodes only, without an a priori node-to-node connectivity. A regularization technique to overcome the singularity-by-construction and to compute all necessary derivatives of the kernel functions is presented. The method combines the simplicity and straightforwardness of the strong-form computational techniques with the advantages of meshfree methods over the classical ones, especially for coupled engineering problems involving moving interfaces. The key features of the proposed approach are: (i) no need to generate a mesh, (ii) simplified imposition of boundary conditions, (iii) no need to evaluate integral forms of governing equations, (iv) applicability to complex irregularly-shaped domains. The proposed STMCM is applied to linear and nonlinear ordinary and partial differential equations of different types and its accuracy and convergence properties are studied. (© 2009 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Toward a solution of a class of non-linear stochastic perturbed PDEs using automated WHEP algorithm

This paper introduces a generalization and automation of the Wiener Hermite expansion with perturbation (WHEP) technique to solve a class of stochastic nonlinear partial differential equations with a perturbed nonlinearity. The automated algorithm generates the deterministic resultant linear equations according to the application of a general linear differential operator and the input parameters. Sample output with different nonlinearities, orders and corrections are presented. The resultant equations are solved numerically and the ensemble average and variance are computed and compared with previous research work. Higher order solutions with higher corrections are computed to show the importance of the generalization of the WHEP technique. The current work extends the use of WHEP for solving stochastic nonlinear differential equations.     

A linear-time algorithm to compute the conjugate of convex piecewise linear-quadratic bivariate functions

We propose the first algorithm to compute the conjugate of a bivariate Piecewise Linear-Quadratic (PLQ) function in optimal linear worst-case time complexity. The key step is to use a planar graph, called the entity graph, not only to represent the entities (vertex, edge, or face) of the domain of a PLQ function but most importantly to record adjacent entities. We traverse the graph using breadth-first search to compute the conjugate of each entity using graph-matrix calculus, and use the adjacency information to create the output data structure in linear time.     

Approximate analytical solutions of fractional gas dynamic equations

In this article, differential transform method (DTM) has been successfully applied to obtain the approximate analytical solutions of the nonlinear homogeneous and non-homogeneous gas dynamic equations, shock wave equation and shallow water equations with fractional order time derivatives. The true beauty of the article is manifested in its emphatic application of Caputo fractional order time derivative on the classical equations with the achievement of the highly accurate solutions by the known series solutions and even for more complicated nonlinear fractional partial differential equations (PDEs). The method is really capable of reducing the size of the computational work besides being effective and convenient for solving fractional nonlinear equations. Numerical results for different particular cases of the equations are depicted through graphs.     

Optimization of Molecular Similarity Index with Applications to Biomolecules

Molecular similarity index measures the similarity between two molecules. Computing the optimal similarity index is a hard global optimization problem. Since the objective function value is very hard to compute and its gradient vector is usually not available, previous research has been based on non-gradient algorithms such as random search and the simplex method. In a recent paper, McMahon and King introduced a Gaussian approximation so that both the function value and the gradient vector can be computed analytically. They then proposed a steepest descent algorithm for computing the optimal similarity index of small molecules. In this paper, we consider a similar problem. Instead of computing atom-based derivatives, we directly compute the derivatives with respect to the six free variables describing the relative positions of the two molecules.. We show that both the function value and gradient vector can be computed analytically and apply the more advanced BFGS method in addition to the steepest descent algorithm. The algorithms are applied to compute the similarities among the 20 amino acids and biomolecules like proteins. Our computational results show that our algorithm can achieve more accuracy than previous methods and has a 6-fold speedup over the steepest descent method.     

Estimate of the Order of Growth of a Class of Entire Functions on the Real Axis

For a class of entire functions we study the problem of estimation of the order of growth of functions on the real axis. This problem is important for the justification of the integral representation of bounded solutions to certain partial differential equations considered in other papers of the authors. In order to obtain an estimate of the order of growth of a function on the real axis, we use the method of differential equations. The method is based, on one hand, on the construction of a system of first-order ordinary differential equations whose solution is a vector function of traces of function and its derivatives on the real axis. On the other hand, under the respective change of variables in the system of equations, we obtain an estimate of the solution to the system of equations for a large positive values of the argument. The obtained estimate is non-trivial and shows the way a complex parameter of a power series affects the order of growth of a function.     

Existence of solutions to Hamilton-Jacobi functional differential equations

This paper deals with the Cauchy problem for nonlinear first order partial functional differential equations. The unknown function is the functional variable in the equation and the partial derivatives appear in a classical sense. A theorem on the local existence of a generalized solution is proved. The initial problem is transformed into a system of functional integral equations for an unknown function and for their partial derivatives with respect to spatial variables. The existence of solutions of this system is proved by using a method of successive approximations. A method of bicharacteristics and integral inequalities are applied.     

Automatic differentiation of iterative processes

Automatic differentiation is used to compute the values of the derivative of a function. If the function is given by a computational graph or code list, then the derivative values can be obtained using the chain rule. An iterative process can be regarded as an infinite code list. It is well known from classical analysis that the limit of the derivatives of the code list is not necessarily equal to the derivative of the limit function. The limit of the derivatives is corect for an important class of iterative processes including generalized Newton methods.     

Numerical solutions of boundary value problems for K-surfaces in R3

A K-surface is a surface whose Gauss curvature K is a positive constant. In this article, we will consider K-surfaces that are defined by a nonlinear boundary value problem. In this setting, existence follows from some recent results on nonlinear second-order elliptic partial differential equations. The analytical techniques used to establish these results motivate effective numerical methods for computing K-surfaces. In theory, the solvability of the boundary value problem reduces to the existence of a subsolution. In an analogous way, we find that if an approximate numerical subsolution can be determined, then the corresponding K-surface can be computed. We will consider two boundary value problems. In the first problem, the K-surface is a graph over a plane. In the second, the K-surface is a radial graph over a sphere. From certain geometrical considerations, it follows that there is a maximum Gauss curvature K_max for these problems. Using a continuation method, we estimate K_max and determine numerically the unique one-parameter family of K-surfaces that exist for K E (0,K_max). This is the first time that this numerical method has been applied to the nonlinear partial differential equations for a K -surface. Sharp estimates for K_max are not available analytically, except in special situations such as a surface of revolution, where the parametrization can be obtained explicitly in terms of elliptic functions. We find that our numerical estimates for K_max are in close agreement with the expected values in these cases. © 1996 John Wiley & Sons, Inc.     

A New defy for iteration methods

The work presents an adaptation of iteration method for solving a class of thirst order partial nonlinear differential equation with mixed derivatives.The class of partial differential equations present here is not solvable with neither the method of Green function, the most usual iteration methods for instance variational iteration method, homotopy perturbation method and Adomian decomposition method, nor integral transform for instance Laplace,Sumudu, Fourier and Mellin transform. We presented the stability and convergence of the used method for solving this class of nonlinear chaotic equations.Using the proposed method, we obtained exact solutions to this kind of equations.     

On the complexity of computing treelength

We resolve the computational complexity of determining the treelength of a graph, thereby solving an open problem of Dourisboure and Gavoille, who introduced this parameter, and asked to determine the complexity of recognizing graphs of a bounded treelength Dourisboure and Gavoille (2007) [6]. While recognizing graphs with treelength 1 is easily seen as equivalent to recognizing chordal graphs, which can be done in linear time, the computational complexity of recognizing graphs with treelength 2 was unknown until this result. We show that the problem of determining whether a given graph has a treelength at most k is NP-complete for every fixed k≥2, and use this result to show that treelength in weighted graphs is hard to approximate within a factor smaller than . Additionally, we show that treelength can be computed in time O^∗(1.7549ⁿ) by giving an exact exponential time algorithm for the Chordal Sandwich problem and showing how this algorithm can be used to compute the treelength of a graph.     

Computing eigenelements of boundary value problems with fractional derivatives

Variational iteration method has been successfully implemented to handle linear and nonlinear differential equations. The main property of the method is its flexibility and ability to solve nonlinear equations accurately and conveniently. In this paper, first, a general framework of the variational iteration method is presented for analytic treatment of differential equations of fractional order where the fractional derivatives are described in Caputo sense. Second, the new framework is used to compute approximate eigenvalues and the corresponding eigenfunctions for boundary value problems with fractional derivatives. Numerical examples are tested to show the pertinent features of this method. This approach provides a new way to investigate eigenvalue problems with fractional order derivatives.     

Computation of the observer gain for extended Luenberger observers using automatic differentiation

For a given nonlinear system, the extended Luenberger observerprovides nearly exact error dynamics. In contrast to the normalform observer, the extended Luenberger observer exists evenif the associated integrability condition is violated. Up tonow, Lie derivatives and Lie brackets required by the designprocedure have been computed symbolically. Even for systemswith moderate size and complexity, one usually obtains extremelylarge expressions for the observer gain. The design of an extendedLuenberger observer based on symbolic differentiation is not feasible for complicated or large-scale systems. In this paperwe discuss a new approach to compute the observer gain. Ourapproach is based on a computation method for derivatives calledautomatic differentiation. In contrast to numeric differentiationby means of divided differences, automatic differentiationincurs no truncation errors.     

Nonlinear wave equations and singular solutions

We construct solutions to nonlinear wave equations that are singular along a prescribed noncharacteristic hypersurface, which is the graph of a function satisfying not the Eikonal but another partial differential equation of the first order. The method of Fuchsian reduction is employed.

     

Sub-exponential graph coloring algorithm for stencil-based Jacobian computations

Partial differential equations can be discretized using a regular Cartesian grid and a stencil-based method to approximate the partial derivatives. The computational effort for determining the associated Jacobian matrix can be reduced. This reduction can be modeled as a (grid) coloring problem. Currently, this problem is solved by using a heuristic approach for general graphs or by developing a formula for every single stencil. We introduce a sub-exponential algorithm using the Lipton–Tarjan separator in a divide-and-conquer approach to compute an optimal coloring. The practical relevance of the algorithm is evaluated when compared with an exponential algorithm and a greedy heuristic.     

Numerical method of mixed finite volume-modified upwind fractional step difference for three-dimensional semiconductor device transient behavior problems

Transient behavior of three-dimensional semiconductor device with heat conduction is described by a coupled mathematical system of four quasi-linear partial differential equations with initial-boundary value conditions. The electric potential is defined by an elliptic equation and it appears in the following three equations via the electric field intensity. The electron concentration and the hole concentration are determined by convection-dominated diffusion equations and the temperature is interpreted by a heat conduction equation. A mixed finite volume element approximation, keeping physical conservation law, is used to get numerical values of the electric potential and the accuracy is improved one order. Two concentrations and the heat conduction are computed by a fractional step method combined with second-order upwind differences. This method can overcome numerical oscillation, dispersion and decreases computational complexity. Then a three-dimensional problem is solved by computing three successive one-dimensional problems where the method of speedup is used and the computational work is greatly shortened. An optimal second-order error estimate in L² norm is derived by using prior estimate theory and other special techniques of partial differential equations. This type of mass-conservative parallel method is important and is most valuable in numerical analysis and application of semiconductor device.