Computing hysteresis points of nonlinear equations depending on two parameters

A direct method is described for computing a hysteresis point (double turning point) corresponding to a cusp point of a system ofn nonlinear equations inn variables depending on two parameters. By addition of two equations a minimally extended system ofn+2 nonlinear equations is constructed for which the hysteresis point is an isolated solution. An efficient implementation of Newton's method is presented not requiring evaluations of second derivatives of the original problem. Two numerical examples show the efficiency of theQ-quadratically convergent method.     

Computing turning points of curves implicitly defined by nonlinear equations depending on a parameter

Let the space curveL be defined implicitly by the (n, n+1) nonlinear systemH(u)=0. A new direct Newton-like method for computing turning points ofL is described that requires per step only the evaluation of one Jacobian and 5 function values ofH. Moreover, a linear system of dimensionn+1 with 4 different right hand sides has to be solved per step. Under suitable conditions the method is shown to converge locally withQ-order two if a certain discretization stepsize is appropriately chosen. Two numerical examples confirm the theoretical results.     

An extended collocation method

Given an approximate solutionx _n of a linear operator equation obtained by a collocation method, an improved solutionx ^* _n+m is obtained fromx _n by an «extended collocation method» which consists in solving a further (m)-order linear system instead of an (n+m)-order one, diminishing the effects of rounding error in carrying out the calculations. For a suitable choice of the knot, the method may be recursively performed both by spline approximation and by algebraic and trigonometric polynomial approximation. A numerical example with a two point boundary value problem confirms the advantages of the extended method with respect to the direct one.     

Solving nonlinear systems of functional equations with fuzzy adaptive simulated annealing

This paper proposes a method for finding solutions of arbitrarily nonlinear systems of functional equations through stochastic global optimization. The original problem (equation solving) is transformed into a global optimization one by synthesizing objective functions whose global minima, if they exist, are also solutions to the original system. The global minimization task is carried out by the stochastic method known as fuzzy adaptive simulated annealing, triggered from different starting points, aiming at finding as many solutions as possible. To demonstrate the efficiency of the proposed method, solutions for several examples of nonlinear systems are presented and compared with results obtained by other approaches. We consider systems composed of n   equations on Euclidean spaces ?n${?}^n$ (n variables: x₁, x₂, x₃, ? , x_n).     

The new extended Jacobian elliptic function expansion algorithm and its applications in nonlinear mathematical physics equations

More recently we have presented the extended Jacobian elliptic function expansion method and its algorithm to seek more types of doubly periodic solutions. Based on the idea of the method, by studying more relations among all twelve kinds of Jacobian elliptic functions. we further extend the method to be a more general method, which is still called the extended Jacobian elliptic function expansion method for convenience. The new method is more powerful to construct more new exact doubly periodic solutions of nonlinear equations. We choose the (2+1)-dimensional dispersive long-wave system to illustrate our algorithm. As a result, twenty-four families of new doubly periodic solutions are obtained. When the modulus m→1 or 0, these doubly periodic solutions degenerate as soliton solutions and trigonometric function solutions. This algorithm can be also applied to other nonlinear equations.     

On the computational complexity of the solution of linear systems with moduli

A problem of solvability for the system of equations of the formAx=D|x|+δ is investigated. This problem is proved to beNP-complete even in the case when the number of equations is equal to the number of variables, the matrixA is nonsingular,A≥D≥0,δ≥0, and it is initially known that the system has a finite (possibly zero) number of solutions. For an arbitrary system ofm equations ofn variables, under additional conditions that the matrixD is nonnegative and its rank is one, a polynomial-time algorithm (of the orderO((max{m, n})³)) has been found which allows to determine whether the system is solvable or not and to find one of such solutions in the case of solvability.     

Analysis of a simple factorization algorithm

The probability that the k^th largest prime factor of a number n is at most n^x is shown to approach a limit F_k(x) as n → ∞. Several interesting properties of F_k(x) are explored, and numerical tables are given. These results are applied to the analysis of an algorithm commonly used to find all prime factors of a given number. The average number of digits in the k^th largest prime factor of a random m-digit number is shown to be asymptotically equivalent to the average length of the k^th longest cycle in a permutation on m objects.     

Note on the principle of stationary phase

The principle of stationary phase as enunciated by Kelvin [1] in 1887 concerns the approximate evaluation of an integral of a rapidly fluctuating function. The well-known formula is derived on the tacit assumption of the amplitude function ?(x) being non-zero at the isolated stationary point ? of the phase function ?(x). The present note points out that the vanishing of ?(x) at this point alters the order of approximation. The significant contribution to the integral comes in this case from the first non-vanishing even order derivative of ?(x) at x = ? and the corresponding formula for the approximate value has been worked out. The formula has been further generalized for the case when the first non-vanishing derivatives of ? and ? are ?ⁿ(α) and ?^m(α), respectively, m, n being both positive integers.     

Two simple and efficient algorithms for Jordan sorting and polygon cutting and clipping

This paper deals with the Jordan sorting problem: Given n intersection points of a Jordan curve with the x-axis in the order in which they occur along the curve, sort these points into the order in which they occur along the x-axis. The worst-case time complexity of this problem is θ(n). Unfortunately, the known O(n) time algorithms are too complicated, which causes that they are difficult to implement and slow for the inputs of sizes that are of practical interest. In this paper, two algorithms for Jordan sorting are presented. The first algorithm is extremely simple. Although its worst-case time complexity is O(nlogn), it is shown that the worst time is achieved only for special inputs. For most inputs, a better performance can be expected. Furthermore, an improved O(nlog logn) worst-case time algorithm is presented. For the input sequences of size from 4 to 10⁵, the algorithms are compared with Quicksort, with the algorithm based on splay trees and with the O(n) time algorithm proposed by Fung et al. The results show that our algorithms are faster. The relevant implementation details are given.     

An efficient solution algorithm for boundary element equations

Boundary element techniques result in the solution of a linear system of equations of the type HU = GQ + B, which can be transformed into a system of equations of the type AX = F. The coefficient matrix A requires the storage of a full matrix on the computer. This storage requirement, of the order of n^*n memory positions (n = number of equations), for a very large n is often considered negative for the boundary element method. Here, two algorithms are presented where the memory requirements to solve the system are only n^*(n - 1)/2 and n^*n/4 respectively. The algorithms do not necessitate any external storage devices nor do they increase the computational efforts.     

An optimal algorithm for constructing the weighted voronoi diagram in the plane

Let S denote a set of n points in the plane such that each point p has assigned a positive weight w(p) which expresses its capability to influence its neighbourhood. In this sense, the weighted distance of an arbitrary point x from p is given by d_e(x,p)/w(p) where d_e denotes the Euclidean distance function. The weighted Voronoi diagram for S is a subdivision of the plane such that each point p in S is associated with a region consisting of all points x in the plane for which p is a weighted nearest point of S.An algorithm which constructs the weighted Voronoi diagram for S in O(n²) time is outlined in this paper. The method is optimal as the diagram can consist of Θ(n²) faces, edges and vertices.     

Exponentially weighted Legendre-Gauss Tau methods for linear second-order differential equations

We develop a method to solve a class of second-order ordinary differential equations with highly oscillatory solutions. The method consists in combining three different techniques: Legendre-Gauss spectral Tau method, exponential fitting, and coefficient perturbation methods. With our approach, the resulting approximate solutions are expressed in terms of an exponentially weighted Legendre polynomial basis {e^ω_nxL_n(x);n≥0}, where ω_n are appropriately chosen complex numbers. The accuracy and efficiency of the method are discussed and illustrated numerically.     

Efficient uncertainty quantification with the polynomial chaos method for stiff systems

The polynomial chaos (PC) method has been widely adopted as a computationally feasible approach for uncertainty quantification (UQ). Most studies to date have focused on non-stiff systems. When stiff systems are considered, implicit numerical integration requires the solution of a non-linear system of equations at every time step. Using the Galerkin approach the size of the system state increases from n to S × n, where S is the number of PC basis functions. Solving such systems with full linear algebra causes the computational cost to increase from O(n³) to O(S³n³). The S³-fold increase can make the computation prohibitive. This paper explores computationally efficient UQ techniques for stiff systems using the PC Galerkin, collocation, and collocation least-squares (LS) formulations. In the Galerkin approach, we propose a modification in the implicit time stepping process using an approximation of the Jacobian matrix to reduce the computational cost. The numerical results show a run time reduction with no negative impact on accuracy. In the stochastic collocation formulation, we propose a least-squares approach based on collocation at a low-discrepancy set of points. Numerical experiments illustrate that the collocation least-squares approach for UQ has similar accuracy with the Galerkin approach, is more efficient, and does not require any modification of the original code.     

Numerische Lösung von Anfangswertaufgaben gewöhnlicher Differentialgleichungen n-ter Ordnung

In the present paper a new method is given for the numerical treatment of the initial problemsy ⁽ⁿ⁾=f(x,y,y′, ...,y ^(n?1),y ⁽ⁱ⁾ (x _o )=y _o ⁽ⁱ⁾ , i=0, 1, ...,n?1. This method is an one-step process of order four. For a class of linear differential equations the exact solution is obtained. Moreover some numerical results are presented.     

On polynomial solutions of the linear stationary control system

It is known that the controllable system x′ = Bx + Du, where the x is the n-dimensional vector, can be transferred from an arbitrary initial state x(0) = x ⁰ to an arbitrary finite state x(T) = x ^T by the control function u(t) in the form of the polynomial in degrees t. In this work, the minimum degree of the polynomial is revised: it is equal to 2p + 1, where the number (p ? 1) is a minimum number of matrices in the controllability matrix (Kalman criterion), whose rank is equal to n. A simpler and a more natural algorithm is obtained, which first brings to the discovery of coefficients of a certain polynomial from the system of algebraic equations with the Wronskian and then, with the aid of differentiation, to the construction of functions of state and control.     

Computing the λ-covers of a string

Given a string x of length n and an integer constant λ, the λ-Cover Problem is defined to be the identification of all the sets of λ substrings each of equal length that cover x. This problem can be solved by a general algorithm in O(n²) time for constant alphabet size. We also generalize the λ-Cover Problem, whereby a set of λ substrings of different lengths are considered, which can be computed using the general algorithm in O(n²) time.     

Computing simple bifurcation points using a minimally extended system of nonlinear equations

The present paper deals with the computation of simple bifurcation points of nonlinear parameter dependent equations. At first, a minimally extended system of nonlinear equations is constructed by addition of one parameter and two equations. This augmented system has an isolated solution which yields to the simple bifurcation point directly. Using the structural properties of this auxiliary system an adapted Newton-like method is developed not requiring evaluations of second derivatives. Finally, the results of some computer experiments show the efficiency of theR-quadratically convergent method.     

Data hiding by an improved exploiting modification direction

This paper represents an improved data hiding scheme, CIE, which uses a codebook to improve the Exploiting Modification Direction (EMD) embedding scheme. In our scheme, one secret (2 ^n?+?x ???1)-ary digit is hidden in a group of pixels in an image as a modified secret digit. Our proposed scheme has an embedding rate $R=\log_2(2^{n+x}-1)/n$ , which is greater than the rate of the EMD scheme, which is R?=?log₂(2n?+?1)/n for n?≥?2 . Embedding rate R is the number of secret bits embedded in each cover pixel. Our experimental results demonstrate that our scheme is able to embed 3 times as many secret bits in an image compared to the original EMD embedding scheme when n?=?2 and x?=?5. Our scheme has low time complexity and achieves this higher embedding performance while retaining reasonable perceptual quality for the image. An experiment verifies these features of our proposed data hiding scheme.     

A program generator for the incomplete cholesky conjugate gradient (ICCG) method with a symmetrizing preprocessor

This paper is an extension of our previous paper “A program generator for the Incomplete LU-decomposition-Conjugate Gradient (ILUCG) method” which appeared in Computer Physics Communications. In that paper we presented a generator program which produced a code package to solve the system of equations Ax = bb, where A is an arbitrary nonsingular matrix, by the ILUCG method. In the present paper we offer an alternative generator program which produces a code package applicable to the case where A is symmetric and positive definite. The numerical algorithm used is the Incomplete Cholesky Conjugate Gradient (ICCG) method of Meijerink and Van der Vorst which executes approximately twice as fast per iteration as the ILUCG method. In addition, we provide an optional preprocessor to treat the case of a not diagonally dominant nonsymmetric and nonsingular matrix A by solving the equation A^TAx = A^Tb.     

The numerical calculation of topological turning points

We introduce the definition of topological turning point of a function ?(x, λ): ?×?→?, then we propose a numerical method for calculating it. This new definition does not require any regularity for ? but its continuity; moreover, topological turning point coincides with turning point when ? is sufficiently smooth. The numerical method that we introduce has linear rate of convergence, and it is of secure convergence.