预条件的平方Smith法求解大型Sylvester矩阵方程

提出了一种预条件的平方Smith算法求解大型连续Sylvester矩阵方程,该算法利用交替方向隐式迭代(ADI)来构造预条件算子,将原方程转换为非对称Stein方程,并在Krylov子空间中应用平方Smith法迭代产生低秩逼近解。数值实验表明,与已知的Jacobi迭代法等算法相比,该算法有更好的迭代效率和收敛精度。     

An algorithm for polynomial matrix factor extraction

An algorithm is described for extracting a polynomial matrix factor featuring any subset of the zeros of a given non-singular polynomial matrix. It is assumed that the zeros to be extracted are given as input data. Complex or repeated zeros are allowed. The algorithm is based on interpolation and relies upon numerically reliable subroutines only. It makes use of a procedure that computes the generalized characteristic vectors of a polynomial matrix at a given point. The extracted factor is provided in column- and row-reduced Popov form. Applications of the algorithm include polynomial matrix interpolation, plus/minus factorization, column- and row-reduction, or computation of the Smith form of a polynomial matrix. The numerical routines described in this paper are implemented in the new release 2.0 of the Polynomial Toolbox for MATLAB.     

Computing diagonal form and Jacobson normal form of a matrix using Gröbner bases

In this paper we present an algorithm for the computation of a diagonal form of a matrix over non-commutative Euclidean domain over a field with the help of Gröbner bases. We propose a general framework of Ore localizations of non-commutative G-algebras and show its merits and constructiveness. It allows us to handle, among others, common operator algebras with rational coefficients.We introduce the splitting of the computation of a normal form (like the Jacobson form over simple domain) for matrices over Ore localizations into the diagonalization (the computation of a diagonal form of a matrix) and the normalization (the computation of the normal form of a diagonal matrix). These ideas are also used for the computation of the Smith normal form in the commutative case. We give a special algorithm for the normalization of a diagonal matrix over the rational Weyl algebra and present counterexamples to its idea over rational shift and q-Weyl algebras.Our implementation of the algorithm in Singular:Plural relies on the fraction-free polynomial strategy, details of which will be described in the forthcoming article. It shows quite an impressive performance, compared with methods which directly use fractions. In particular, we experience quite a moderate swell of coefficients and obtain uncomplicated transformation matrices. We leave questions on the algorithmic complexity of this algorithm open, but we stress the practical applicability of the proposed method to a large class of non-commutative algebras.     

Reduction of Smith Normal Form Transformation Matrices

Smith normal form computations are important in group theory, module theory and number theory. We consider the transformation matrices for the Smith normal form over the integers and give a presentation of arbitrary transformation matrices for this normal form. Our main contribution is an algorithm that replaces already computed transformation matrices by others with small entries. We combine methods from lattice basis reduction with a procedure to reduce the sum of the squared entries of both transformation matrices. This algorithm performs well even for matrices of large dimensions.     

Smith forms overR[z_{1},z_{2}]

Relationships between a polynomial matrix and its Smith forms are explored. It is shown, for example, that a matrix overR[z_{1}, z_{2}]is equivalent to its Smith form overR[z_{1}, z_{2}]if and only if a certain system of linear polynomial equations has a solution.     

A New variant of the McEliece cryptosystem based on the Smith form of convolutional codes

In this article, the authors propose a new version of the McEliece cryptosystem based on the Smith form of convolutional codes. They use the Smith form to hide a part of the code in the public matrix, and they leave the other part secret. The secret part will then be used for decryption. They hide this part by multiplying it on the left by a random matrix, and they add a random matrix which has a few conditions. Their scheme has a small public key size compared to the original McEliece scheme and resists the unique decoding attack against convolutional structure presented at the conference PQCrypto 2013 by Landais and Tillich. Further, the exhaustive search attack is infeasible on their system.     

Generalized Subresultants for Computing the Smith Normal Form of Polynomial Matrices

We describe a new algorithm for the computation of the Smith normal form of polynomial matrices. This algorithm computes the normal form and pre- and post-multipliers in deterministic polynomial time. Noticing that the computation reduces to a linear algebra problem over the field of the coefficients, we obtain a good worst-case complexity bound.     

Part I-Smith form and common divisor of polynomial matrices

Polynomial matrices play an important part in linear system calculations. New computational procedures are given for calculation of the Smith normal form and the greatest common right divisor of polynomial matrices. It is shown how suitable transformation matrices can be determined for the calculation of the Smith normal form, and how a set of polynomial matrix multipliers can be calculated for the greatest common right divisor problem. Neither of these algorithms relies on explicit calculation of the greate3t common divisor of polynomials. Limited numerical experience has shown that the3e algorithms are both fast and accurate.     

Parametric models of linear multivariable systems for adaptive control

This paper presents a parametrization method for direct adaptive control of linear multivariable systems with strictly proper discrete-time or continuous-time transfer functions. The necessary a priori information is shown to be a diagonal matrix with the noninvertible zeros of the Smith form and appropriate polynomial degrees.     

Realization algorithms for systems over a principal ideal domain

In this paper realization algorithms for systems over a principal ideal domain are described. This is done using the Smith form or a modified Hermite form for matrices over a principal ideal domain. It is shown that Ho's algorithm and an algorithm due to Zeiger can be generalized to the ring case. Also a recursive realization algorithm, including some results concerning the partial realization problem, is presented. Applications to systems over the integers, delay differential systems and two-dimensional systems are discussed.     

Equivalence of a matrix over R [s,z] with its Smith form

Conditions under which a matrix over R[s, z] is equivalent, to its Smith form are investigated. These conditions involve the concept of zeros of a matrix over R[s, z] which has not been previously encountered in this context.     

Compatible coarsening in the multigraph algorithm

We present some heuristics incorporating the philosophy of compatible relaxation into an existing algebraic multigrid method, the so-called multigraph solver of Bank and Smith [Bank Randolph E., Kent Smith R. An algebraic multilevel multigraph algorithm. SIAM J Sci Comput 2002;25:1572–92]. In particular, approximate left and right eigenvectors of the iteration matrix for the smoother are used in computing both the sparsity pattern and the numerical values of the transfer matrices that correspond to restriction and prolongation. Some numerical examples illustrate the effectiveness of the procedure.     

Fast computation of the Smith form of a sparse integer matrix

We present a new probabilistic algorithm to compute the Smith normal form of a sparse integer matrix . The algorithm treats A as a “black box”—A is only used to compute matrix-vector products and we do not access individual entries in A directly. The algorithm requires about black box evaluations for word-sized primes p and , plus additional bit operations. For sparse matrices this represents a substantial improvement over previously known algorithms. The new algorithm suffers from no “fill-in” or intermediate value explosion, and uses very little additional space. We also present an asymptotically fast algorithm for dense matrices which requires about bit operations, where O(MM(m)) operations are sufficient to multiply two matrices over a field. Both algorithms are probabilistic of the Monte Carlo type — on any input they return the correct answer with a controllable, exponentially small probability of error. Received: March 9, 2000.     

基于自适应Smith算法的烧制窑温控策略

陶瓷、页岩砖、硅砖烧制过程中的烧制窑温度控制是过程控制研究主要课题.自适应Smith算法在对强扰动系统、大滞后温度系统的控制上有一定优势.该文提出一种自适应Smith算法,构成一种新的自适应Smith烧制窑温度控制策略.软件仿真及实际应用表明:该自适应Smith算法是一种有效解决温控问题的算法,抗干扰能力强,应用前景广...     

Error Analysis and Comparison of Two Algorithms Measuring Compensated Income

We analyze and compare the errors of two numerical approaches for measuring compensated income. We prove that Vartia’s algorithm and Breslaw and Smith’s algorithm both converge quadratically; when the price change within each partition step is small, the error of Vartia’s algorithm is approximately half that of Breslaw and Smith’s algorithm. A theorem and the appropriate simulations with three different demand systems correct the existing error analysis of the two algorithms, and demonstrate that Vartia’s algorithm is more accurate than Breslaw and Smith’s.     

Computation of the transfer function matrix and its Laurent expansion of generalized two-dimensional systems

An algorithm is developed for the computation of the transfer function matrix of a two-dimensional system, which is given in its generalized form. The algorithm is a recursion in terms of the original system matrix and does not require the inversion of a two-variable polynomial matrix. An algorithm for the evaluation of the Laurent expansion of the inverse of a two-variable polynomial matrix is also presented.     

基于Smith预估的模糊PID主动队列管理算法研究

为解决网络拥塞控制系统中由于网络大时滞对主动队列管理算法产生不利影响的问题,提出了一种基于Smith预估的模糊PID主动队列管理算法.该算法将Smith预估控制与模糊控制相结合,利用Smith预估器补偿网络时滞,同时运用模糊控制在一定程度上克服了传统Smith预估器对模型结构与参数的精确性过于敏感、鲁棒性差的缺点,使主动队列管理算法控制性能有明显提高.仿真实验结果表明,该算法在大时滞的网络环境下能很好地将路由器队列长度收敛于期望值,并能适应突发流和非弹性业务流的干扰,适用于动态变化的网络环境.     

Eigenstructure assignment in a class of second-order dynamic systems

Eigenstructure assignment using the proportional-plus-derivative feedback controller in a class of secondorder dynamic system is investigated. Simple, general, complete parametric expressions for both the closed-loop eigenvector matrix and the feedback gains are established based on two simple Smith form reductions. The approach utilizes directly the original system data and involves manipulations only on n?dimensional matrices. Furthermore, it reveals all the degrees of freedom which can be further utilized to achieve additional system specifications. An example shows the effect of the proposed approach.