Search

Abstract: 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 -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 -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. [Copyright &y& Elsevier]

Abstract: Compressive sampling offers a new paradigm for acquiring signals that are compressible with respect to an orthonormal basis. The major algorithmic challenge in compressive sampling is to approximate a compressible signal from noisy samples. This paper describes a new iterative recovery algorithm called CoSaMP that delivers the same guarantees as the best optimization-based approaches. Moreover, this algorithm offers rigorous bounds on computational cost and storage. It is likely to be extremely efficient for practical problems because it requires only matrix–vector multiplies with the sampling matrix. For compressible signals, the running time is just , where N is the length of the signal. [Copyright &y& Elsevier]

Abstract: The concept of a -basis was introduced in the case of parametrized curves in 1998 and generalized to the case of rational ruled surfaces in 2001. The -basis can be used to recover the parametric equation as well as to derive the implicit equation of a rational curve or surface. Furthermore, it can be used for surface reparametrization and computation of singular points. In this paper, we generalize the notion of a -basis to an arbitrary rational parametric surface. We show that: (1) the -basis of a rational surface always exists, the geometric significance of which is that any rational surface can be expressed as the intersection of three moving planes without extraneous factors; (2) the -basis is in fact a basis of the moving plane module of the rational surface; and (3) the -basis is a basis of the corresponding moving surface ideal of the rational surface when the base points are local complete intersections. As a by-product, a new algorithm is presented for computing the implicit equation of a rational surface from the -basis. Examples provide evidence that the new algorithm is superior than the traditional algorithm based on direct computation of a Gröbner basis. Problems for further research are also discussed. [Copyright &y& Elsevier]

Abstract: A well-known lemma of Suslin says that for a commutative ring if is unimodular where is monic and , then there exist such that the ideal generated by equals . This lemma played a central role in the resolution of Serre’s Conjecture. In the case where contains a set of cardinality greater than such that is invertible for each in , we prove that the can simply correspond to the elementary operations , , where . These efficient elementary operations enable us to give new and simple algorithms for reducing unimodular rows with entries in to using elementary operations in the case where is an infinite field. Another feature of this paper is that it shows that the concrete local–global principles can produce competitive complexity bounds. [Copyright &y& Elsevier]

Abstract: Let be a finite group. It is easy to compute the character of corresponding to a given complex representation, but much more difficult to compute a representation affording a given character. In part this is due to the fact that a class of equivalent representations contains no natural canonical representation. Although there is a large literature devoted to computing representations, and methods are known for particular classes of groups, we know of no general method which has been proposed which is practical for any but small groups. We shall describe an algorithm for computing an irreducible matrix representation which affords a given character of a given group . The algorithm uses properties of the structure of which can be computed efficiently by a program such as GAP, theoretical results from representation theory, theorems from group theory (including the classification of finite simple groups), and linear algebra. All results in this paper have been implemented in the GAP package REPSN. [Copyright &y& Elsevier]

For a Viterbi-like algorithm over a sectionalized trellis of a linear block code, the decoding procedure consists of three parts: computing the metrics of the edges, selecting the survivor edge between each pair of adjacent vertices and determining the survivor path from the origin to each vertex. In this paper, some new methods for computing the metrics of the edges are proposed. Our method of “partition of index set” for computing the metrics is shown to be near-optimal. The proposed methods are then applied to Reed–Muller (RM) codes. For some RM codes, the computational complexity of decoding is significantly reduced in comparison to the best-known ones. For the RM codes, a direct method for constructing their trellis-oriented-generator-matrices is proposed and some shift invariances are deduced. [Copyright &y& Elsevier]