Algorithms for solution of systems of linear diophantine equations in residue fields

Algorithms are proposed for computing the basis of the solution set of a system of linear Diophantine homogeneous or inhomogeneous equations in the residue field modulo a prime number. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 2, pp. 15–23, March–April 2007.     

Compatibility of Systems of Linear Constraints over the Set of Natural Numbers

Criteria of compatibility of a system of linear Diophantine equations, strict inequations, and nonstrict inequations are considered. Upper bounds for components of a minimal set of solutions and algorithms of construction of minimal generating sets of solutions for all types of systems are given. These criteria and the corresponding algorithms for constructing a minimal supporting set of solutions can be used in solving all the considered types of systems and systems of mixed types.     

Algorithms for solving systems of linear diophantine equations in residue rings

Algorithms are proposed that construct the basis of the set of solutions to a system of homogeneous or inhomogeneous linear Diophantine equations in a residue ring modulo n when the prime factors of n are known. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 27–40, November–December 2007.     

Algorithms for solving systems of linear diophantine equations in integer domains

Algorithms are described that solve homogeneous systems of linear Diophantine equations over natural numbers and over the set {0, 1}. Properties of the algorithms and their time estimates are given. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 2, pp. 3–17, March–April 2006.     

Solution of systems of linear algebraic equations with preliminary flattening

A method of improving computing properties of matrices of systems of linear algebraic equations is considered. Translated from Kibernetika i Sistemnyi Analiz, No. 5, pp. 144–149, September–October, 1999.     

Ellipsoidal bounds for uncertain linear equations and dynamical systems

In this paper, we discuss semidefinite relaxation techniques for computing minimal size ellipsoids that bound the solution set of a system of uncertain linear equations. The proposed technique is based on the combination of a quadratic embedding of the uncertainty, and the -procedure. This formulation leads to convex optimization problems that can be essentially solved in O(n³)—n being the size of unknown vector—by means of suitable interior point barrier methods, as well as to closed form results in some particular cases. We further show that the uncertain linear equations paradigm can be directly applied to various state-bounding problems for dynamical systems subject to set-valued noise and model uncertainty.     

Characterizing the solution set of polynomial systems in terms of homogeneous forms: an LMI approach

This paper considers the problem of determining the solution set of polynomial systems, a well‐known problem in control system analysis and design. A novel approach is developed as a viable alternative to the commonly employed algebraic geometry and homotopy methods. The first result of the paper shows that the solution set of the polynomial system belongs to the kernel of a suitable symmetric matrix. Such a matrix is obtained via the solution of a linear matrix inequality (LMI) involving the maximization of the minimum eigenvalue of an affine family of symmetric matrices. The second result concerns the computation of the solution set from the kernel of the obtained matrix. For polynomial systems of degree m in n variables, a basic procedure is available if the kernel dimension does not exceed m+1, while an extended procedure can be applied if the kernel dimension is less than n(m?1)+2. Finally, some application examples are illustrated to show the features of the approach and to make a brief comparison with polynomial resultant techniques. Copyright © 2003 John Wiley & Sons, Ltd.     

Approximate solution of a system of linear integral equations by the Taylor expansion method

A simple and efficient approximate technique is developed to obtain the solution to a system of linear integral equations. This technique is based on the Taylor expansion. The method has been successfully applied to determine approximate solutions of a system of Fredholm integral equations and Volterra integral equations of not only the second kind but also the first kind. The mth order approximation of the solution is exact up to a polynomial of degree equal to or less than m. Several illustrative examples are presented to show the effectiveness and accuracy of this method.     

Analysis of the properties of a linear system using the method of artificial basis matrices

Formulas relating elements of the method in adjacent basis matrices are used to solve a system of linear algebraic equations and to represent analytically the general solutions to the corresponding system of linear algebraic inequalities for a nondegenerate constraint matrix. Sponsored by the ICS NATO program of April 18 2006, in line with the Project “Optimal replacement of information technologies and stable development (in Kazakhstan, Ukraine, and the USA),” NATO Grant CLG 982209. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 4, pp. 119–127, July–August 2007.     

Solving systems of linear equations with Boolean variables

The paper presents a method to solve systems of linear equations with Boolean variables, which implements an enumeration strategy. Necessary and sufficient conditions for the existence of feasible plans are formalized. A formal procedure to analyze subsets of alternatives is described. The structure of an algorithm that possesses the property of completeness is presented. Special cases of systems of equations are examined. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 5, pp. 42–50, September–October 2006.     

Parallel,iterative solution of sparse linear systems: Models and architectures

Solving large, sparse, linear systems of equations is a fundamental problems in large scale scientific and engineering computation. A model of a general class of asynchronous, iterative solution methods for linear systems is developed. In the model, the system is solved by creating several cooperating tasks that each compute a portion of the solution vector. A data transfer model predicting both the probability that data must be transferred between two tasks and the amount of data to be transferred is presented. This model is used to derive an execution time model for predicting parallel execution time and an optimal number of tasks given the dimension and sparsity of the coefficient matrix and the costs of computation, synchronization, and communication.The suitability of different parallel architectures for solving randomly sparse linear systems is discussed. Based on the complexity of task scheduling, one parallel architecture, based on a broadcast bus, is presented and analyzed.     

Parallel Gauss-Jordan elimination for the solution of dense linear systems

Any factorization/back substitution scheme for the solution of linear systems consists of two phases which are different in nature, and hence may be inefficient for parallel implementation on a single computational network. The Gauss-Jordan elimination scheme unifies the nature of the two phases of the solution process and thus seems to be more suitable for parallel architectures, especially if reconfiguration of the communication pattern is not permitted. In this communication, a computational network for the Gauss-Jordan algorithm is presented. This network compares favorably with optimal implementations of the Gauss elimination/back substitution algorithm.     

Direct methods of solving systems of linear algebraic ef ions with complex a-matrices

Algorithms of computer algebra are proposed for solving systems of linear algebraic equations with complex á- matrices. An analysis of roundoff errors for the computational schemes considered is given. Translated from Kibernetika i Sistemnyi Analiz, No. 2, pp. 144–156, March–April, 2000.     

Vector extrapolation methods with applications to solution of large systems of equations and to PageRank computations

An important problem that arises in different areas of science and engineering is that of computing the limits of sequences of vectors {x_n}, where with N very large. Such sequences arise, for example, in the solution of systems of linear or nonlinear equations by fixed-point iterative methods, and lim_n→∞x_n are simply the required solutions. In most cases of interest, however, these sequences converge to their limits extremely slowly. One practical way to make the sequences {x_n} converge more quickly is to apply to them vector extrapolation methods. In this work, we review two polynomial-type vector extrapolation methods that have proved to be very efficient convergence accelerators; namely, the minimal polynomial extrapolation (MPE) and the reduced rank extrapolation (RRE). We discuss the derivation of these methods, describe the most accurate and stable algorithms for their implementation along with the effective modes of usage in solving systems of equations, nonlinear as well as linear, and present their convergence and stability theory. We also discuss their close connection with the method of Arnoldi and with GMRES, two well-known Krylov subspace methods for linear systems. We show that they can be used very effectively to obtain the dominant eigenvectors of large sparse matrices when the corresponding eigenvalues are known, and provide the relevant theory as well. One such problem is that of computing the PageRank of the Google matrix, which we discuss in detail. In addition, we show that a recent extrapolation method of Kamvar et al. that was proposed for computing the PageRank is very closely related to MPE. We present a generalization of the method of Kamvar et al. along with a very economical algorithm for this generalization. We also provide the missing convergence theory for it.     

Nearly optimal solution of rational linear systems of equations with symbolic lifting and numerical initialization

Hensel’s symbolic lifting is a highly effective method for the solution of a general or structured (e.g. Toeplitz or Hankel) linear system of equations with integer or rational coefficients of bounded length. It can handle ill conditioned inputs, for which numerical methods become costly. Lifting amounts to recursive multiplications by vectors of the input coefficient matrices and its precomputed inverse modulo a fixed integer s. Such multiplications only involve small numbers of data movements and arithmetic operations with bounded precision. The known methods for precomputation of the inverse are more costly, however; in particular they involve more data movements. As our remedy for this bottleneck stage we create an auxiliary matrix sharing its inverse modulo s with the input matrix, and we readily compute this inverse by applying numerical iterative refinement, which is a numerical counterpart of lifting. In the case of general unstructured as well as Toeplitz, Hankel, and other popular structured inputs our hybrid algorithms involve a small number of data movements and optimal number of Boolean (that is bitwise) operations (up to a logarithmic factor). We extend the algorithms to nearly optimal computation of polynomial greatest common divisors (gcds), least common multiples (lcms) and Padé approximations, as well as the Berlekamp-Massey reconstruction of linear recurrences. We also cover Newton’s lifting for matrix inversion, specialize it to the case of structured input, and combine it with Hensel’s to enhance the overall efficiency. Our initialization techniques work for Newton’s lifting as well. Furthermore we extend all our lifting algorithms to allow their initialization modulo powers of two, thus implementing them in the binary base.     

Fast methods for the iterative solution of linear elliptic and parabolic partial differential equations involving 2 space dimensions

Within the last decade, attention has been devoted to the introduction of several fast computational methods for solving the linear difference equations which are derived from the finite difference discretisation of many standard partial differential equations of Mathematical Physics.

In this paper, the authors develop and extend an exact factorisation technique previously applied to parabolic equations in one space dimension to the implicit difference equations which are derived from the application of alternating direction implicit methods when applied to elliptic and parabolic partial differential equations in 2 space dimensions under a variety of boundary conditions.     

On the Moser- and super-reduction algorithms of systems of linear differential equations and their complexity

The notion of irreducible forms of systems of linear differential equations with formal power series coefficients as defined by Moser [Moser, J., 1960. The order of a singularity in Fuchs’ theory. Math. Z. 379–398] and its generalisation, the super-irreducible forms introduced in Hilali and Wazner [Hilali, A., Wazner, A., 1987. Formes super-irréductibles des systèmes différentiels linéaires. Numer. Math. 50, 429–449], are important concepts in the context of the symbolic resolution of systems of linear differential equations [Barkatou, M., 1997. An algorithm to compute the exponential part of a formal fundamental matrix solution of a linear differential system. Journal of App. Alg. in Eng. Comm. and Comp. 8 (1), 1–23; Pflügel, E., 1998. Résolution symbolique des systèmes différentiels linéaires. Ph.D. Thesis, LMC-IMAG; Pflügel, E., 2000. Effective formal reduction of linear differential systems. Appl. Alg. Eng. Comm. Comp., 10 (2) 153–187]. In this paper, we reduce the task of computing a super-irreducible form to that of computing one or several Moser-irreducible forms, using a block-reduction algorithm. This algorithm works on the system directly without converting it to more general types of systems as needed in our previous paper [Barkatou, M., Pflügel, E., 2007. Computing super-irreducible forms of systems of linear differential equations via Moser-reduction: A new approach. In: Proceedings of ISSAC’07. ACM Press, Waterloo, Canada, pp. 1–8]. We perform a cost analysis of our algorithm in order to give the complexity of the super-reduction in terms of the dimension and the Poincaré-rank of the input system. We compare our method with previous algorithms and show that, for systems of big size, the direct block-reduction method is more efficient.