Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA local construction of the Smith normal form of a matrix polynomial
193
0
0.0
(
0
)
Added by
Jon Wilkening
Publication date
2010
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We present an algorithm for computing a Smith form with multipliers of a regular matrix polynomial over a field. This algorithm differs from previous ones in that it computes a local Smith form for each irreducible factor in the determinant separately and then combines them into a global Smith form, whereas other algorithms apply a sequence of unimodular row and column operations to the original matrix. The performance of the algorithm in exact arithmetic is reported for several test cases.
rate research
Read More
Computational problem certificates are additional data structures for each output, which can be used by a-possibly randomized-verification algorithm that proves the correctness of each output. In this paper, we give an algorithm that computes a certificate for the minimal polynomial of sparse or structured nxn matrices over an abstract field, of sufficiently large cardinality, whose Monte Carlo verification complexity requires a single matrix-vector multiplication and a linear number of extra field operations. We also propose a novel preconditioner that ensures irreducibility of the characteristic polynomial of the generically preconditioned matrix. This preconditioner takes linear time to be applied and uses only two random entries. We then combine these two techniques to give algorithms that compute certificates for the determinant, and thus for the characteristic polynomial, whose Monte Carlo verification complexity is therefore also linear.
This paper describes and analyzes a method for computing border bases of a zero-dimensional ideal $I$. The criterion used in the computation involves specific commutation polynomials and leads to an algorithm and an implementation extending the one provided in [MT05]. This general border basis algorithm weakens the monomial ordering requirement for grob bases computations. It is up to date the most general setting for representing quotient algebras, embedding into a single formalism Grobner bases, Macaulay bases and new representation that do not fit into the previous categories. With this formalism we show how the syzygies of the border basis are generated by commutation relations. We also show that our construction of normal form is stable under small perturbations of the ideal, if the number of solutions remains constant. This new feature for a symbolic algorithm has a huge impact on the practical efficiency as it is illustrated by the experiments on classical benchmark polynomial systems, at the end of the paper.
We present a non-commutative algorithm for the multiplication of a 2x2-block-matrix by its transpose using 5 block products (3 recursive calls and 2 general products) over C or any finite field.We use geometric considerations on the space of bilinear forms describing 2x2 matrix products to obtain this algorithm and we show how to reduce the number of involved additions.The resulting algorithm for arbitrary dimensions is a reduction of multiplication of a matrix by its transpose to general matrix product, improving by a constant factor previously known reductions.Finally we propose schedules with low memory footprint that support a fast and memory efficient practical implementation over a finite field.To conclude, we show how to use our result in LDLT factorization.
In this paper we report on an application of computer algebra in which mathematical puzzles are generated of a type that had been widely used in mathematics contests by a large number of participants worldwide. The algorithmic aspect of our work provides a method to compute rational solutions of single polynomial equations that are typically large with $10^2 ldots 10^5$ terms and that are heavily underdetermined. This functionality was obtained by adding modules for a new type of splitting of equations to the existing package CRACK that is normally used to solve polynomial algebraic and differential systems.
The main contribution of this manuscript is a local normal form for Hamiltonian actions of Poisson-Lie groups $K$ on a symplectic manifold equipped with an $AN$-valued moment map, where $AN$ is the dual Poisson-Lie group of $K$. Our proof uses the delinearization theorem of Alekseev which relates a classical Hamiltonian action of $K$ with $mathfrak{k}^*$-valued moment map to a Hamiltonian action with an $AN$-valued moment map, via a deformation of symplectic structures. We obtain our main result by proving a ``delinearization commutes with symplectic quotients theorem which is also of independent interest, and then putting this together with the local normal form theorem for classical Hamiltonian actions wtih $mathfrak{k}^*$-valued moment maps. A key ingredient for our main result is the delinearization $mathcal{D}(omega_{can})$ of the canonical symplectic structure on $T^*K$, so we additionally take some steps toward explicit computations of $mathcal{D}(omega_{can})$. In particular, in the case $K=SU(2)$, we obtain explicit formulas for the matrix coefficients of $mathcal{D}(omega_{can})$ with respect to a natural choice of coordinates on $T^*SU(2)$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
