Mixed Volume Computation for Semi-Mixed Systems

Abstract. The Li—Li algorithm produced in [11] for the mixed volume computation of fully mixed polynomial systems is reconstructed in this article for general semi-mixed polynomial systems. Taking the special structure of the semi-mixed supports of the systems into account, the resulting algorithm, illustrated by numerical results, can dramatically speed up the mixed volume computation, especially when the systems are unmixed. Even when applied to fully mixed systems, the new algorithm improves the speed of the Li—Li algorithm by a considerable amount.     

Mixed Volume Computation for Semi-Mixed Systems

   Abstract. The Li—Li algorithm produced in [11] for the mixed volume computation of fully mixed polynomial systems is reconstructed in this article for general semi-mixed polynomial systems. Taking the special structure of the semi-mixed supports of the systems into account, the resulting algorithm, illustrated by numerical results, can dramatically speed up the mixed volume computation, especially when the systems are unmixed. Even when applied to fully mixed systems, the new algorithm improves the speed of the Li—Li algorithm by a considerable amount.     

Stability analysis for Lotka–Volterra systems based on an algorithm of real root isolation

Based on the theory of monotone flows of solutions of systems of differential equations, the Routh–Hurwitz theorem and a real root isolation algorithm of multivariate polynomials are applied to a class of Lotka–Volterra diffusion systems. An algorithm to determine the location of equilibria and the stability of the nonlinear dynamics systems is implemented in Maple.     

A QMR-based interior-point algorithm for solving linear programs

A new approach for the implementation of interior-point methods for solving linear programs is proposed. Its main feature is the iterative solution of the symmetric, but highly indefinite 2×2-block systems of linear equations that arise within the interior-point algorithm. These linear systems are solved by a symmetric variant of the quasi-minimal residual (QMR) algorithm, which is an iterative solver for general linear systems. The symmetric QMR algorithm can be combined with indefinite preconditioners, which is crucial for the efficient solution of highly indefinite linear systems, yet it still fully exploits the symmetry of the linear systems to be solved. To support the use of the symmetric QMR iteration, a novel stable reduction of the original unsymmetric 3×3-block systems to symmetric 2×2-block systems is introduced, and a measure for a low relative accuracy for the solution of these linear systems within the interior-point algorithm is proposed. Some indefinite preconditioners are discussed. Finally, we report results of a few preliminary numerical experiments to illustrate the features of the new approach.     

An improved harmony search algorithm for synchronization of discrete-time chaotic systems

The harmony search (HS) algorithm is a recently developed meta-heuristic algorithm, and has been very successful in a wide variety of optimization problems. HS was conceptualized using an analogy with music improvisation process where music players improvise the pitches of their instruments to obtain better harmony. The HS algorithm does not require initial values and uses a random search instead of a gradient search, so derivative information is unnecessary. Furthermore, the HS algorithm is simple in concept, few in parameters, easy in implementation, imposes fewer mathematical requirements, and does not require initial value settings of the decision variables. In recent years, the investigation of synchronization and control problem for discrete chaotic systems has attracted much attention, and many possible applications. The tuning of a proportional–integral–derivative (PID) controller based on an improved HS (IHS) algorithm for synchronization of two identical discrete chaotic systems subject the different initial conditions is investigated in this paper. Simulation results of the IHS to determine the PID parameters to synchronization of two Hénon chaotic systems are compared with other HS approaches including classical HS and global-best HS. Numerical results reveal that the proposed IHS method is a powerful search and controller design optimization tool for synchronization of chaotic systems.     

The strong chromatic number of partial triple systems

A strong colouring of a hypergraph is an assignment of colours to its vertices so that no two vertices in a hyperedge have the same colour. We establish that strong colouring of partial triple systems is NP-complete, even when the number of colours is any fixed k≥3. In contrast, an efficient algorithm is given for strong colouring of maximal partial triple systems. Observations in this algorithm underpin a complete determination of the spectrum of strong chromatic numbers for maximal partial triple systems.     

Balanced POD for model reduction of linear PDE systems: convergence theory

We consider convergence analysis for a model reduction algorithm for a class of linear infinite dimensional systems. The algorithm computes an approximate balanced truncation of the system using solution snapshots of specific linear infinite dimensional differential equations. The algorithm is related to the proper orthogonal decomposition, and it was first proposed for systems of ordinary differential equations by Rowley (Int. J. Bifurc. Chaos Appl. Sci. Eng. 15(3):997?C1013, 2005). For the convergence analysis, we consider the algorithm in terms of the Hankel operator of the system, rather than the product of the system Gramians as originally proposed by Rowley. For exponentially stable systems with bounded finite rank input and output operators, we prove that the balanced realization can be expressed in terms of balancing modes, which are related to the Hankel operator. The balancing modes are required to be smooth, and this can cause computational difficulties for PDE systems. We show how this smoothness requirement can be lessened for parabolic systems, and we also propose a variation of the algorithm that avoids the smoothness requirement for general systems. We prove entrywise convergence of the matrices in the approximate reduced order models in both cases, and present numerical results for two example PDE systems.     

Optimal parametric synthesis of continuous/discrete stochastic terminal control systems

We propose an efficient numerical algorithm for computer parametric synthesis of linear continuous/discrete stochastic dynamic terminal control systems. The algorithm is based on the application of the method of inverse-conjugate systems and conjugate variables. Translated fromDinamicheskie Sistemy, Vol. 11, 1992.     

A variable dimension fixed point algorithm and the orientation of simplices

A variable dimension algorithm with integer labelling is proposed for solving systems ofn equations inn variables. The algorithm is an integer labelling version of the 2-ray algorithm proposed by the author. The orientation of lower dimensional simplices is studied and is shown to be preserved along a sequence of adjacent simplices.     

Fast solution of unsymmetric banded Toeplitz systems by means of spectral factorizations and Woodbury's formula

A fast algorithm for solving systems of linear equations with banded Toeplitz matrices is studied. An important step in the algorithm is a novel method for the spectral factorization of the generating function associated with the Toeplitz matrix. The spectral factorization is extracted from the right deflating subspaces corresponding to the eigenvalues inside and outside the open unit disk of a companion matrix pencil constructed from the coefficients of the generating function. The factorization is followed by the Woodbury inversion formula and solution of several banded triangular systems. Stability of the algorithm is discussed and its performance is demonstrated by numerical experiments. Copyright © 2012 John Wiley & Sons, Ltd.     

A procedure to calculate torsion¶of elliptic curves over ℚ

We present an algorithm which uses the analytic parameterization of elliptic curves to rapidly calculate torsion subgroups, and calculate its running time. This algorithm is much faster than the “traditional” Lutz–Nagell algorithm used by most computer algebra systems to calculate torsion subgroups. Received: 7 August 1997 / Revised version: 28 November 1997     

Auxiliary model identification method for multirate multi-input systems based on least squares

This paper derives state-space models for multirate multi-input sampled-data systems. Based on the corresponding transfer function models, an auxiliary model based recursive least squares algorithm is presented to identify the parameters of the multirate systems from the multirate input–output data. Further, convergence properties of the proposed algorithm are analyzed. Finally, an illustrative example is given.     

Newton's method for the solution of systems of equalities and inequalities

An algorithm is constructed generalizing Newton's method to apply to the solution of systems of nonlinear equations and inequalities. It is proved that the convergence of the algorithm is of the second order.Translated from Matematicheskie Zametki, Vol. 8, No. 5, pp. 635–640, November, 1970.     

An efficient algorithm for solving rank one perturbed linear Diophantine systems using Rosser��s approach

Recently, we described a generalization of Rosser’s algorithm for a single linear Diophantine equation to an algorithm for solving systems of linear Diophantine equations. Here, we make use of the new formulation to present a new algorithm for solving rank one perturbed linear Diophantine systems, based on using Rosser’s approach. Finally, we compare the efficiency and effectiveness of our proposed algorithm with the algorithm proposed by Amini and Mahdavi-Amiri (Optim Methods Softw 21:819–831, 2006).     

Extending the eigCG algorithm to nonsymmetric Lanczos for linear systems with multiple right‐hand sides

The technique that was used to build the eigCG algorithm for sparse symmetric linear systems is extended to the nonsymmetric case using the BiCG algorithm. We show that, similar to the symmetric case, we can build an algorithm that is capable of computing a few smallest magnitude eigenvalues and their corresponding left and right eigenvectors of a nonsymmetric matrix using only a small window of the BiCG residuals while simultaneously solving a linear system with that matrix. For a system with multiple right‐hand sides, we give an algorithm that computes incrementally more eigenvalues while solving the first few systems and then uses the computed eigenvectors to deflate BiCGStab for the remaining systems. Our experiments on various test problems, including Lattice QCD, show the remarkable ability of eigBiCG to compute spectral approximations with accuracy comparable with that of the unrestarted, nonsymmetric Lanczos. Furthermore, our incremental eigBiCG followed by appropriately restarted and deflated BiCGStab provides a competitive method for systems with multiple right‐hand sides. Copyright © 2013 John Wiley & Sons, Ltd.     

Modified multiscale permutation entropy algorithm and its application for multiscroll chaotic systems

To analyze the complexity of continuous chaotic systems better, the modified multiscale permutation entropy (MMPE) algorithm is proposed. Characteristics and parameter choices of the MMPE algorithm are investigated. The comparative study between MPE and MMPE shows that MMPE has better robustness for identifying different chaotic systems when the scale factor τ takes large values. Compared with MPE, MMPE algorithm is more suitable for analyzing the complexity of time series as it has τ time series. For its application, MMPE algorithm is used to calculate the complexity of multiscroll chaotic systems. Results show that complexity of multiscroll chaotic systems does not increase as scroll number increases. Discussions based on first‐order difference operation present a reasonable explanation on why the complexity does not increase. This complexity analysis method lays a theoretical as well as experimental basis for the applications of multiscroll chaotic systems. © 2014 Wiley Periodicals, Inc. Complexity 21: 52–58, 2016     

LP narrowing: A new strategy for finding all solutions of nonlinear equations

An efficient algorithm is proposed for finding all solutions of systems of n nonlinear equations. This algorithm is based on interval analysis and a new strategy called LP narrowing. In the LP narrowing strategy, boxes (n-dimensional rectangles in the solution domain) containing no solution are excluded, and boxes containing solutions are narrowed so that no solution is lost by using linear programming techniques. Since the LP narrowing is very powerful, all solutions can be found very efficiently. By numerical examples, it is shown that the proposed algorithm could find all solutions of systems of 5000-50,000 nonlinear equations in practical computation time.     

Analysis of nonautonomous systems of ordinary differential equations with exponentially periodic matrix

We investigate a class of nonautonomous systems of ordinary differential equations whose matrix can be characterized as exponentially periodic. We develop the algorithm of spectral analysis of these systems. By this algorithm we prove reducibility theorems. The proposed algorithm is based on the splitting method that allows to reduce considered systems to simpler ones with quasidiagonal matrix, and formulate constructive conditions of solutions stability.     

Efficient implementation of the Barnes-Hut octree algorithm for Monte Carlo simulations of charged systems

Computer simulation with Monte Carlo is an important tool to investigate the function and equilibrium properties of many biological and soft matter materials solvable in solvents.The appropriate treatment of long-range electrostatic interaction is essential for these charged systems,but remains a challenging problem for large-scale simulations.We develop an efficient Barnes-Hut treecode algorithm for electrostatic evaluation in Monte Carlo simulations of Coulomb many-body systems.The algorithm is based on a divide-and-conquer strategy and fast update of the octree data structure in each trial move through a local adjustment procedure.We test the accuracy of the tree algorithm,and use it to perform computer simulations of electric double layer near a spherical interface.It is shown that the computational cost of the Monte Carlo method with treecode acceleration scales as log N in each move.For a typical system with ten thousand particles,by using the new algorithm,the speed has been improved by two orders of magnitude from the direct summation.     

Level structure of Zhegalkin polynomials,properties of test sets,and an annihilator search algorithm

Properties of the Boolean functions specified by the Zhegalkin polynomials in n variables of degree not greater than k are investigated from the viewpoint of placing their unit (zero) points on a unit cube. Properties of test sets for the Zhegalkin polynomials are considered, where the key role is played by the irredundant test sets. A deterministic algorithm for finding all the annihilators for a given polynomial is described including minimal-degree annihilators that have applications in cryptology. In the available algorithms for finding annihilators, the problem is reduced to solving systems of linear Boolean equations. Reducing the dimension of these systems decreases the algorithmic complexity of solving the problem. The proposed algorithm makes it possible to decrease the complexity of finding annihilators by reducing the dimension of such systems but it does not reduce the asymptotic complexity of solving systems of linear Boolean equations.