Search

This paper is devoted to the application aspects of homomorphic cryptography. It provides a description of a fully homomorphic matrix polynomial-based encryption scheme. It also gives the results of practical comparison of fully homomorphic encryption schemes. We consider some special cases of homomorphic encryption allowing computations of a limited number of functions.

We take up a systematic study of all steps to derive a proof of [5, Lemma 2] from that of [1, Lemma 6.8.3].

We obtain a representation of the solution to the Cauchy problem with a polynomial difference operator. We establish the solvability condition and specify it in the twodimensional case. Bibliography: 9 titles.

Let L be the Laplace matrix of a weighted digraph. The aim of the paper is to establish a simple way for computing any coefficient of the characteristic polynomial of L as a constant sign sum over the incoming spanning forests. The idea is to express L as the product of generalized (weighted) incidence matrices. It turns out that the minors of them can be studied in terms of the tree-like structure of the digraph. This makes it possible to compute the minors of L.

A polynomial with exactly two critical values is called a generalized Chebyshev polynomial (or Shabat polynomial). A polynomial with exactly three critical values is called a Zolotarev polynomial. Two Chebyshev polynomials f and g are called Z-homotopic if there exists a family pα, α\( \epsilon \) [0, 1], where p0 = f, p1 = g, and pα is a Zolotarev polynomial if α\( \epsilon \) (0, 1). As each Chebyshev polynomial defines a plane tree (and vice versa), Z-homotopy can be defined for plane trees. In this work, we prove some necessary geometric conditions for the existence of Z-homotopy of plane trees, describe Z-homotopy for trees with five and six edges, and study one interesting example in the class of trees with seven edges.

We investigate the structure of polynomial matrices in connection with their reducibility by semiscalarequivalent transformations to simpler forms. We obtain a system of invariants for one class of matrices with respect to semiscalar equivalence. On this basis, we establish the almost canonical form of a matrix with respect to semiscalar equivalence.

For a matrix pencil A 0 x − A 1 , where A 0 and A 1 are (n × n) -matrices over an arbitrary field F , and A0 is a nonsingular matrix, we establish the normal form with respect to semiscalar equivalence. We also describe the structure of nonsingular polynomial matrices over the field F , which can be reduced to the established form by the transformations of semiscalar equivalence.

In this paper, some properties of the Wiedemann–Coppersmith algorithm are studied. In particular, when the matrix of a linear system is symmetric, an orthogonal basis of the Krylov space is constructed with the help of approximations of formal series from odd steps of this algorithm. We propose some modifications that use the described properties.

The paper discusses the method of rank factorization for solving spectral problems for two-parameter polynomial matrices. New forms of rank factorization, which are computed using unimodular matrices only, are suggested. Applications of these factorizations to solving spectral problems for two-parameter polynomial matrices of both general and special forms are presented. In particular, matrices free of the singular spectrum are considered. Conditions sufficient for a matrix to be free of the singular spectrum and also conditions sufficient for a basis matrix of the null-space to have neither the finite regular nor the finite singular spectrum are provided. Bibliography: 3 titles.

The paper considers the eigenvalve problem for a polynomial m × n matrix F(μ) of rank ρ. Algorithms. allowing one to reduce this problem to the generalized matrix eigenvalve problem are suggested. The algorithms are based on combining rank factorization methods with the method of hereditary pencils. Methods for exhausting the subspaces of polynomial solutions of zero index from the matrix nullspaces and for isolating the regular kernel from F(μ), with its subsequent linearization, are proposed. Bibliography: 6 titles.

In 1984, the author suggested an algorithm for solving systems of polynomial equations. Now we modify it and improve the bounds on its complexity as well as the degrees and lengths of coefficients from the ground filed of the elements constructed by this algorithm. Bibliography: 4 titles.

The problem of separation of a regular factor from a matrix polynomial has been of interest to mathematicians for a long time because the solution of this problem gives a method for the determination of roots of matrix one-sided equations. Various methods of contemporary mathematics are used for the solution of this problem. In 1956, Lopatyns’kyi, in terms of systems of differential equations, gave necessary and sufficient conditions for representation of a matrix in the form of the product of regular factors with coprime determinants. Gochberg, Lancaster, and Rodman in [7] and Malyshev in [4] solve this problem by the methods of Jordan chains. In [3], Kazimirs’kyi proposes an essentially new approach to the problem of separation of a regular divisor from a matrix polynomial. This approach is based on the notions of a determining matrix and values of a matrix on a system of roots of a polynomial. In these terms, Kazimirs’kyi established necessary and sufficient conditions for the existence of these divisors and proposes a method for their determination. The obtained results hold for polynomial matrices over an algebraically closed field of characteristic zero. The specific feature of methods of solution and terms used in the representation of results do not enable one to generalize these methods for wider classes of fields. This generalization became possible after work [2] in which the Kazimirs’kyi results are represented in another form. In the present paper, we investigate polynomial matrices over an infinite field. Under certain restrictions on the canonical diagonal form of a divisor, necessary and sufficient conditions for its existence are established. It is worth noting that, after the solution of the problem of separation of a regular divisor by Kazimirs’kyi, the number of works devoted to regular divisors sharply dropped. Problems of description of nonassociative divisors of matrices [6, 10] and representation of matrices in the form of the product of several factors with preassigned characteristics [5, 8, 13] have attracted the attention of researchers. Let F be a field and let A(x) be a nonsingular (n × n) matrix over F[x] representable in the form of a matrix polynomial over the field F : A(x) = A k x k + A k−1 x k−1 +… + A 0 . The matrix A(x) is called monic if A k = E is an identity matrix of order k and regular if det A k ≠ 0. We say that the matrix A(x) is right regularizable if there exists an invertible matrix U (x) such that

A complex n × n matrix A is said to be nonderogatory if the degree of its minimal polynomial is equal to the degree of the characteristic polynomial. The aim of the paper is to prove the following assertion: Let $ A\bar{A} $ be a nonderogatory matrix with real positive spectrum. Then A can be made real by a unitary congruence transformation if and only if A and $ \bar{A} $ are unitarily congruent. Bibliography: 5 titles.

An approach to solving spectral problems for multiparameter polynomial matrices based on passing to accompanying pencils of matrices is described. Also reduction of spectral problems for multiparameter pencils of complex matrices to the corresponding real problems is considered. Bibliography: 6 titles.

We investigate multiplication algorithms for dense and sparse polynomials and polynomial matrices over different numerical domains and obtain expressions for the complexity of multiplication of polynomials and polynomial matrices understood as the expectation of the number of arithmetic operations. These expressions for a set of parameters of practical interest are tabulated. The results of experiments with the corresponding programs are presented. Bibliography: 8 titles.

The known balance relation interrelating the spectrum multiplicities and the sums of mini-indices of a one-parameter polynomial matrix with its degree and rank is generalized to the case of a multiparameter polynomial matrix. Bibliography: 6 titles.

The notion of indicial rational function is introduced for ordinary differential equations with polynomial coefficients and polynomial right-hand sides, and algorithms for its construction are proposed.

Let {ie910-01} be a field and let {ie910-02} be a finite-dimensional {ie910-03}-algebra. We define the length of a finite generating set of this algebra as the smallest number k such that words of length not greater than k generate {ie910-04} as a vector space, and the length of the algebra is the maximum of the lengths of its generating sets. In this article, we give a series of examples of length computation for matrix subalgebras. In particular, we evaluate the lengths of certain upper triangular matrix subalgebras and their direct sums, and the lengths of classical commutative matrix subalgebras. The connection between the length of an algebra and the lengths of its subalgebras is also studied.

The paper considers the problem of computing zeros of scalar polynomials in several variables. The zeros of a polynomial are subdivided into the regular (eigen-and mixed) zeros and the singular ones. An algorithm for computing regular zeros, based on a decomposition of a given polynomial into a product of primitive polynomials, is suggested. The algorithm is applied to solving systems of nonlinear algebraic equations. Bibliography: 5 titles.

Polynomial approximations of functions on a family of unconnected continua is studied. The case of two hal-valls is considered. Bibliography: 3 titles.

We give an effective solution of the conjugacy problem for two-by-two matrices over the polynomial ring in one variable over a finite field.

A new method (the RP-q method) for factorizing scalar polynomials in q variables and q-parameter polynomial matrices (q ≥ 1) of full rank is suggested. Applications of the algorithm to solving systems of nonlinear algebraic equations and some spectral problems for a q-parameter polynomial matrix F (such as separation of the eigenspectrum and mixed spectrum of F, computation of bases with prescribed spectral properties of the null-space of polynomial solutions of F, and computation of the hereditary polynomials of F) are considered. Bibliography: 10 titles.

The conditions of arbitrarily exact polynomial approximation of functions continuous on a closed interval with respect to an unbounded sign-sensitive weight are obtained by using divided differences with multiple nodes.

The paper continues the development of rank-factorization methods for solving certain algebraic problems for multi-parameter polynomial matrices and introduces a new rank factorization of a q-parameter polynomial m × n matrix F of full row rank (called the PG-q factorization) of the form F = PG, where $$P = \prod\limits_{k = 1}^{q - 1} {\prod\limits_{i = 1}^{n_k } {\nabla _i^{(k)} } } $$ is the greatest left divisor of F; Δ i (k) i is a regular (q-k)-parameter polynomial matrix the characteristic polynomial of which is a primitive polynomial over the ring of polynomials in q-k-1 variables, and G is a q-parameter polynomial matrix of rank m. The PG-q algorithm is suggested, and its applications to solving some problems of algebra are presented. Bibliography: 6 titles.

For a q-parameter polynomial m × n matrix F of rank ρ, solutions of the equation Fx = 0 at points of the spectrum of the matrix F determined by the (q −1)-dimensional solutions of the system Z[F] = 0 are considered. Here, Z[F] is the polynomial vector whose components are all possible minors of order ρ of the matrix F. A classification of spectral pairs in terms of the matrix A[F], with which the vector Z[F] is associated, is suggested. For matrices F of full rank, a classification and properties of spectral pairs in terms of the so-called levels of heredity of points of the spectrum of F are also presented. Bibliography: 4 titles.

Known types of resultant matrices corresponding to one-parameter matrix polynomials are generalized to the multiparameter case. Based on the resultant approach suggested, methods for solving the following problems for multiparameter polynomial matrices are developed: computing a basis of the matrix range, computing a minimal basis of the right null-space, and constructing the Jordan chains and semilattices of vectors associated with a multiple spectrum point. In solving these problems, the original polynomial matrix is not transformed. Methods for solving other parametric problems of algebra can be developed on the basis of the method for computing a minimal basis of the null-space of a polynomial matrix. Issues concerning the optimality of computing the null-spaces of sparse resultant matrices and numerical precision are not considered. Bibliography: 19 titles.

We reexamine the Wiedemann—Coppersmith—Kaltofen—Villard algorithm for randomized computation of the determinant of an integer matrix and substantially simplify and accelerate its bottleneck stage of computing the minimum generating matrix polynomial, to make the algorithm practically promising while keeping it asymptotically fast. Bibliography: 58 titles.

The algorithm of ∇V-factorization, suggested earlier for decomposing one- and two-parameter polynomial matrices of full row rank into a product of two matrices (a regular one, whose spectrum coincides with the finite regular spectrum of the original matrix, and a matrix of full row rank, whose singular spectrum coincides with the singular spectrum of the original matrix, whereas the regular spectrum is empty), is extended to the case of q-parameter (q ≥ 1) polynomial matrices. The algorithm of ∇V-q factorization is described, and its justification and properties for matrices with arbitrary number of parameters are presented. Applications of the algorithm to computing irreducible factorizations of q-parameter matrices, to determining a free basis of the null-space of polynomial solutions of a matrix, and to finding matrix divisors corresponding to divisors of its characteristic polynomial are considered. Bibliogrhaphy: 4 titles.

The paper continues the investigation of methods for factorizing q-parameter polynomial matrices and considers their applications to solving multiparameter problems of algebra. An extension of the AB-algorithm, suggested earlier as a method for solving spectral problems for matrix pencils of the form A - λB, to the case of q-parameter (q ≥ 1) polynomial matrices of full rank is proposed. In accordance with the AB-algorithm, a finite sequence of q-parameter polynomial matrices such that every subsequent matrix provides a basis of the null-space of polynomial solutions of its transposed predecessor is constructed. A certain rule for selecting specific basis matrices is described. Applications of the AB-algorithm to computing complete polynomials of a q-parameter polynomial matrix and exhausting them from the regular spectrum of the matrix, to constructing irreducible factorizations of rational matrices satisfying certain assumptions, and to computing “free” bases of the null-spaces of polynomial solutions of an arbitrary q-parameter polynomial matrix are considered. Bibliography: 7 titles.

Definitions of certain spectral characteristics of polynomial matrices (such as the analytical (algebraic) and geometric multiplicities of a point of the spectrum, deflating subspaces, matrix solvents, and block eigenvalues and eigenvectors) are generalized to the multiparameter case, and properties of these characteristics are analyzed. Bibliogrhaphy: 4 titles.

For polynomial matrices of full rank, including matrices of the form A - λI and A - λB, numerical methods for solving the following problems are suggested: find the divisors of a polynomial matrix whose spectra coincide with the zeros of known divisors of its characteristic polynomial; compute the greatest common divisor of a sequence of polynomial matrices; solve the inverse eigenvalue problem for a polynomial matrix. The methods proposed are based on the ΔW and ΔV factorizations of polynomial matrices. Applications of these methods to the solution of certain algebraic problems are considered. Bibliography: 3 titles.

For a q-parameter (q ≥ 2) polynomial matrix of full rank whose regular and singular spectra have no points in common, a method for computing its partial relative factorization into a product of two matrices with disjoint spectra is suggested. One of the factors is regular and is represented as a product of q matrices with disjoint spectra. The spectrum of each of the factors is independent of one of the parameters and forms in the space ℂq a cylindrical manifold w.r.t. this parameter. The method is applied to computing zeros of the minimal polynomial with the corresponding eigenvectors. An application of the method to computing a specific basis of the null-space of polynomial solutions of the matrix is considered. Bibliography: 4 titles.

Methods for solving the partial eigenproblem for multiparameter regular pencils of real matrices, which allow one to improve given approximations of an eigenvector and the associated point of the spectrum (both finite and infinite) are suggested. Ways of extending the methods to complex matrices, polynomial matrices, and coupled multiparameter problems are indicated. Bibliography: 10 titles.

Methods for computing polynomials (complete polynomials) whose zeros form cylindrical manifolds of the regular spectrum of a q-parameter polynomial matrix in the space ℂq are considered. Based on the method of partial relative factorization of matrices, new methods for computing cylindrical manifolds are suggested. The ΨW and ΨV methods, previously proposed for computing complete polynomials of q-parameter polynomial matrices whose regular spectrum is independent of one of the parameters, are extended to a wider class of matrices. Bibliography: 4 titles.

Methods for computing scalar and vector spectral characteristics of a polynomial matrix are proposed. These methods are based on determining the so-called generating vectors (eigenvectors and principal vectors) by using the method of rank factorization of polynomial matrices. The possibility of extending the methods to the case of two-parameter polynomial matrices is indicated. Bibliography: 4 titles.

The notion of a complete polynomial of a multiparameter polynomial matrix, generalizing that of an invariant polynomial of a one-parameter polynomial matrix, is introduced. Methods for computing complete polynomials are suggested. Applications of these methods to various spectral problems for polynomial matrices are considered. Bibliography: 7 titles.

Spaces of multiparameter rational vectors, i.e., of vectors whose components are rational functions in several variables, and polynomial bases of their subspaces are considered. The conjecture that any subspace in the space of multiparameter rational vectors possesses a “free” polynomial basis, i.e., a basis such that the associated basis multiparameter polynomial matrix has no finite regular spectrum, is disproved by an example. Some consequences of this fact are indicated. Simpler proofs of some properties of the singular spectra of basis polynomial matrices corresponding to the null-spaces of a singular polynomial matrix are presented. Bibliography: 5 titles.

The method of rank factorization (the Δ W-q method), previously suggested by the author as a method for solving algebraic problems for a multiparameter matrix F polynomially dependent on parameters, is applied to analyze the finite spectrum of F. Special attention is paid to the part of the spectrum σ[F] of the q-parameter matrix F whose points are independent of at least one of the spectral parameters. Bibliography: 6 titles.

We present two methods of computing the characteristic polynomial of an endomorphism of a free module over a commutative domain. The methods require O(n3) and O(nlog7) ring operations, respectively. Bibliography: 6 titles.

Recent progress in polynomial root-finding relies on employing the associated companion and generalized companion DPR1 matrices. (“DPR1” stands for “diagonal plus rank-one.”) We propose an algorithm that uses nearly linear arithmetic time to square a DPR1 matrix. Consequently, the algorithm squares the roots of the associated characteristic polynomial. This incorporates the classical techniques of polynomial root-finding by means of root-squaring into a new effective framework. Our approach is distinct from the earlier fast methods for squaring companion matrices. Bibliography: 13 titles.

The notion of a generating eigenvector of a multiparameter polynomial matrix, generalizing the notion of an eigenvector of a one-parameter polynomial matrix, is introduced. Some properties of generating eigenvectors are established, and two methods for constructing them are suggested. Bibliography: 6 titles.

The problem on polynomial approximation of functions from some class defined on a compact set E of the complex plane is studied. The case where E is the union of a finite number of segments is considered. Bibliography:12 titles.

In the present paper, methods and algorithms for numerical solution of spectral problems and some problems in algebra related to them for one- and two-parameter polynomial and rational matrices are considered. A survey of known methods of solving spectral problems for polynomial matrices that are based on the rank factorization of constant matrices, i.e., that apply the singular value decomposition (SVD) and the normalized decomposition (the QR factorization), is given. The approach to the construction of methods that makes use of rank factorization is extended to one- and two-parameter polynomial and rational matrices. Methods and algorithms for solving some parametric problems in algebra based on ideas of rank factorization are presented. Bibliography: 326titles.

We solve the problem of semiscalar equivalence of polynomial matrices to the Smith canonical form diag(1, ϕ(x), ..., ϕ(x)) from the condition that the polynomial ϕ(x) has simple roots.

We find necessary and sufficient conditions for the existence of a factorization of symmetric matrices over polynomial rings with involution.

We consider finite sets of numerical matrices and the polynomial matrices corresponding to them that have the Smith form diag (1, ϕ(x), ..., ϕ(x)). We solve the problem of reducing such sets to canonical form with one similarity transformation assuming that all the roots of the invariant polynomial ϕ(x) are simple.

We establish a condition for the existence of common unital divisors of polynomial matrices over an arbitrary field, with the divisors having a prescribed characteristic polynomial. The results obtained are applied to find a common solution of matrix polynomial equations.