Solving Index Form Equations in Fields of Degree 9 with Cubic Subfields

We describe an efficient algorithm for solving index form equations in number fields of degree 9 which are composites of cubic fields with coprime discriminants. We develop the algorithm in detail for the case of complex cubic fields, but the main steps of the procedure are also applicable for other cases. Our most important tool is the main theorem of a recent paper of Gaál (1998a). In view of this result the index form equation in the ninth degree field implies relative index form equations over the subfields. In our case these equations are cubic relative Thue equations over cubic fields. The main purpose of the paper is to show that this approach is much more efficient than the direct method, which consists of reducing the index form equation to unit equations over the normal closure of the original field. At the end of the paper we describe our computational experience. Many ideas of the paper can be applied to develop fast algorithms for solving index form equations in other types of higher degree fields which are composites of subfields.     

Finding Intersections and Normalizers in Finitely Generated Nilpotent Groups

We present algorithms for computing intersections, normalizers and subgroup products of subgroups in finitely generated nilpotent groups given by nilpotent presentations. The problems are reduced to solving for certain minimal solutions in linear Diophantine equations over the integers. Performance of the algorithm using a Mathematica implementation is demonstrated.     

On solving Diophantine equations by real matrix manipulation

This note presents simple algorithms for obtaining the solutions of the Diophantine equation. Our methods can produce classes of all solutions with lower degree than a specified number. The previous algorithms involve some troublesome computations, e.g., the calculation of both the controllability indexes and the observability indexes or the solution of a pole assignment problem, etc. Our contribution is that our algorithm requires only basic matrix operations such as addition, subtraction, multiplication, and inversion of given real matrices. In addition, by solving simple linear equations, the class of all minimum degree solutions can be given. Therefore the computational efforts are reduced compared with previous algorithms     

A note on solving linear Diophantine systems by using L 3-reduction algorithm

The main difficulty in solving linear Diophantine systems is the very rapid growth of intermediate results which makes many algorithms, for solving linear Diophantine systems, impractical even for large computers. One way for controlling this growth is to use the L ³-reduction algorithm, introduced by Lenstra et al. [A.K. Lenstra, H.W. Lenstra, and L. Lov?sz, Factoring polynomials with rational coefficients, Math. Ann. 261 (1982), pp. 515–534.]. Esmaeili [H. Esmaeili, How can we solve a linear Diophantine equation by the basis reduction algorithm, Int. J. Comput. Math. 82 (2005), pp. 1227–1234.] proposed a method for obtaining the general integer solution of a linear Diophantine equation by using L ³-reduction algorithm. Here we propose a procedure for generalizing Esmaeili's method, to a method for obtaining the general integer solution of systems of linear Diophantine equations by using L ³-reduction algorithm. Then we consider the complexity issues and show that the generalized algorithm controls the growth of the intermediate results and the number of required arithmetic operations well. Finally, some illustrative numerical examples are given to show the efficiency of the proposed algorithm.     

Partial algorithms for satellite unknowns determination

The concept of satellite unknowns with respect to a set of selected unknowns in linear homogeneous differential systems was introduced earlier by the author of this paper, and an algorithm for satellite unknowns testing was proposed. On one of the stages of this algorithm, it is required to compare Picard–Vessiot extensions of two differential systems constructed in the course of the algorithm operation. The commonly accepted method of solving this problem, which is based on Hrushovski’s algorithm, has rather high algorithmic complexity, which hampers its use in practice. In the paper, some partial algorithms for satellite unknowns testing are described. These algorithms are not always applicable but have relatively low computational complexity and can be implemented in computer algebra systems.     

广义系统Wiener状态滤波新算法

应用时域上的现代时间序列分析方法，基于ARMA新息模型和白噪声估计理论，由一种新的非递推最优状态估值器的递推变形，提出了广义系统Wiener状态滤波的一种新算法，它可统一处理滤波、平滑和预报问题，且具有渐近稳定性。同某些算法相比，它避免了求解Riccati方程和Diophantine方程，且避免了计算伪逆，因而减小了计算负担。仿真例子说明了其有效性。     

A simple equation solver and its application to financial modelling

We discuss a simple algorithm for solving sets of simultaneous equations. The algorithm can solve systems of linear and some kinds of non-linear equations, although it has nowhere near the power of a general non-linear equation solver. Its principal advantages over more general algorithms are simplicity and speed. Versions of the algorithm have been used in a graphics language and in a system for interactively modifying the equations that constitute financial models. We discuss the second application in more detail here.     

Constructive algorithm for system immersion into non-linear observer form

There exists a class of non-linear systems which cannot be transformed into a non-linear observer form (an observable linear system up to output injection) via diffeomorphism, but can be immersed into a higher dimensional non-linear observer form. This class of systems can be characterized by a differential equation called characteristic equation. If the system is an n dimensional system and it is immersible into n?+?m dimensional observer form, the characteristic equation involves n?+?m?+?1 unknowns where n?+?m unknowns are for the state immersion and one for the output transformation. In general, one should solve these unknowns simultaneously which makes the characterization difficult. After investigating the algebraic structure of the characteristic equation, we present an algorithm to check the immersibility under a constant rank assumption. Using the algorithm, one can check the immersibility iteratively since only one unknown is involved at each step of the algorithm.     

On the Euler-Imshenetskii-Darboux transformation of linear second-order equations

It is shown how the linear Euler-Imshenetskii-Darboux (EID) differential transformation can be used for generating infinite sequences of linear second-order ordinary differential equations starting from certain standard equations. In so doing, the method of factorization of differential operators and operator identities obtained by means of this method are used. Generalizations of some well-known integrable cases of the Schrödinger equation are found. An example of an integrable equation with the Liouville coefficients, which apparently cannot be solved by the well-known Kovacic and Singer algorithms and their modifications, is constructed. An algorithm for solving the constructed class of equations has been created and implemented in the computer algebra system REDUCE. The corresponding procedure GENERATE is a supplement to the ODESOLVE procedure available in REDUCE. Solutions of some equations by means of the GENERATE procedure in REDUCE 3.8, as well as those obtained by means of DSOLVE in Maple 10, are presented. Although the algorithm based on the Euler-Imshenetskii-Darboux transformation is not an alternative to the existing algorithms for solving linear second-order ordinary differential equations, it is rather efficient within the limits of its applicability.     

Solution of progressively changing equilibrium equations for nonlinear structures

In the analysis of nonlinear structures by tangent stiffness methods, the equilibrium equations change progressively during the analysis. When direct methods of solving these equations are used, it may be possible to re-use a substantial part of the previously reduced coefficient matrix, and hence substantially reduce the equation solving effort. This paper examines procedures for re-solving equations when only selected parts of the reduced matrix need to be modified.The Crout and Cholesky algorithms are first reviewed for initial complete reduction and subsequent selective reduction of the coefficient matrix, and it is shown that the Cholesky algorithm is superior for selective reduction. A general procedure is then presented for identifying those parts of the coefficient matrix which remain unchanged as the structure changes. Finally, a general purpose in-core equation solver is presented, in which those parts of the previously reduced matrix which need to be modified are determined automatically during the solution process, and only these portions are changed. The equation solver is based on the Cholesky algorithm, and is applicable to both positive-definite and well conditioned non-positive-definite symmetrical systems of equations.     

Parallel direct linear system solvers -- a survey

This paper is a survey of direct parallel algorithms for solving systems of linear equations. We present an up-to-date collection of algorithms for solving triangular, dense, and tridiagonal systems of equations. We state their resulting speedup over the corresponding sequential algorithms, and evaluate their numerical stability, whenever possible.     

Methods of solution and criteria of consistency of systems of linear diophantine equations over the set of natural numbers1

Some methods and algorithms of solution of systems of linear Diophantine equations over the naturals are briefly reviewed. Criteria and an incremental algorithm of efficient solution of the problem of consistency for a system of linear Diophantine equations and inequalities over the naturals are given. This research was supported under grant INTAS-RFBR 95-0095. Translated from Kibernetika i Sistemnyi Analiz, No. 4, pp. 12–36, July–August, 1999.     

A recursive algorithm for coprime fractions and Diophantineequations

The computation of coprime fractions for proper rational matrices and the solving of the minimal design problem are important in the design of multivariable systems by using polynomial fractional terms. A recursive algorithm, which fully exploits the shift-invariant property of the generalized resultants, is developed to carry out these computations. A method for solving the Diophantine equation that is based on this algorithm is outlined. This results in a significant reduction in computation as compared to the standard methods involving solution of linear algebraic equations. Some comparisons to existing methods show that the present algorithm is computationally more attractive with regard to efficiency and accuracy     

基于即时学习的MIMO系统滑模预测控制方法

针对MIMO非线性系统的控制问题,采用数据驱动的控制策略,将具有本质自适应能力的即时学习算法与具有强鲁棒性的滑模预测控制相结合,设计了一种基于即时学习的滑模预测（LL-SMPC）控制方法．该方法在在线局部建模的基础上,采用滑模预测控制律求取最优控制量,具有较强的自适应和抗干扰能力,并避免TDiophantine方程的求解,有效减少了计算量．通过仿真研究,验证了算法的有效性．     

Offline-Enhanced Reduced Basis Method Through Adaptive Construction of the Surrogate Training Set

The reduced basis method (RBM) is a popular certified model reduction approach for solving parametrized partial differential equations. One critical stage of the offline portion of the algorithm is a greedy algorithm, requiring maximization of an error estimate over parameter space. In practice this maximization is usually performed by replacing the parameter domain continuum with a discrete “training” set. When the dimension of parameter space is large, it is necessary to significantly increase the size of this training set in order to effectively search parameter space. Large training sets diminish the attractiveness of RBM algorithms since this proportionally increases the cost of the offline phase. In this work we propose novel strategies for offline RBM algorithms that mitigate the computational difficulty of maximizing error estimates over a training set. The main idea is to identify a subset of the training set, a “surrogate training set” (STS), on which to perform greedy algorithms. The STS we construct is much smaller in size than the full training set, yet our examples suggest that it is accurate enough to induce the solution manifold of interest at the current offline RBM iteration. We propose two algorithms to construct the STS: our first algorithm, the successive maximization method, is inspired by inverse transform sampling for non-standard univariate probability distributions. The second constructs an STS by identifying pivots in the Cholesky decomposition of an approximate error correlation matrix. We demonstrate the algorithm through numerical experiments, showing that it is capable of accelerating offline RBM procedures without degrading accuracy, assuming that the solution manifold has rapidly decaying Kolmogorov width.     

Reducing the wrapping effect

When solving ODEs by interval methods, the main difficulty is reducing the wrapping effect. Various solutions have been put forward, all of which are applicable for narrow initial intervals or to particular classes of equations only. This paper describes an algorithm which, instead of intervals, uses a larger family of sets. The algorithm exhibits a very small wrapping effect and applies to any type of equation and initial region. For the time being it handles only two-dimensional equations.     

On the polynomial equations for the MIMO LQ stochastic regulator

The role played by three polynomial equations in the LQ stochastic regulation problem is discussed. The emphasis is on establishing conditions under which the LQ regulator can be obtained via the solution of a single uncoupled Diophantine equation. Nevertheless, the authors do not claim that there is any advantage in solving a single uncoupled equation in place of two coupled Diophantine equations     

Post-quantum signature algorithms on noncommutative algebras,using difficulty of solving systems of quadratic equations

A recently proposed new concept for constructing algebraic signature schemes with a hidden group is used to develop two new post-quantum signature algorithms on four-dimensional and six-dimensional finite noncommutative associative algebras. As in the case of the post-quantum signature schemes of multivariate cryptography, the security of the introduced algorithms is based on the computational difficulty of solving systems of many quadratic equations (44 and 42) with many unknowns (40 and 36). The signature represents a pair of a natural number e and a vector S. The latter enters three times in the verification equation used, providing resistance to the forging signature attacks by using the value S as a fitting parameter. A public key is generated in the form of a set of vectors, each of which is calculated as the product of triples of secret vectors. With a special choice of these triples, a signer has the possibility of calculating a signature that satisfies the verification equation. The developed post-quantum signature algorithms are practical, having sufficiently small signatures (97 and 109 bytes), public keys (387 and 291 bytes), and secret keys (315 and 451 bytes). A significant difference from the public-key algorithms of multivariate cryptography is that in the developed signature schemes, the system of quadratic equations is derived from the formulas for generating the public-key elements in the form of a set of vectors of m-dimensional finite noncommutative algebra with an associative vector multiplication operation. The formulas define the system of n quadratic vector equations, which reduces to the system of m quadratic equations over a finite field.     

Certified dense linear system solving

A randomized algorithm is given for solving a system of linear equations over a principal ideal domain. The algorithm returns a solution vector which has minimal denominator. A certificate of minimality is also computed. A given system has a Diophantine solution precisely when the minimal denominator is one. Cost estimates are given for systems over the ring of integers and ring of polynomials with coefficients from a field.     

A new block algorithm for full-rank solution of the Sylvester-observer equation

A new block algorithm for computing a full rank solution of the Sylvester-observer equation arising in state estimation is proposed. The major computational kernels of this algorithm are: 1) solutions of standard Sylvester equations, in each case of which one of the matrices is of much smaller order than that of the system matrix and (furthermore, this small matrix can be chosen arbitrarily), and 2) orthogonal reduction of small order matrices. There are numerically stable algorithms for performing these tasks including the Krylov-subspace methods for solving large and sparse Sylvester equations. The proposed algorithm is also rich in Level 3 Basic Linear Algebra Subroutine (BLAS-3) computations and is thus suitable for high performance computing. Furthermore, the results on numerical experiments on some benchmark examples show that the algorithm has better accuracy than that of some of the existing block algorithms for this problem.