Lower bounds for the bilinear complexity of associative algebras

Let R(A) denote the bilinear complexity (also called rank) of a finite dimensional associative algebra A.?We prove that if the decomposition of into simple algebras contains only noncommutative factors, that is, the division algebra is noncommutative or . In particular, -matrix multiplication requires at least essential bilinear multiplications. We also derive lower bounds of the form essential bilinear multiplications. We also derive lower bounds of the form for the algebra of upper triangular -matrices and the algebra of truncated bivariate polynomials in the indeterminates X,Y over some field k.?A class of algebras that has received wide attention in this context con-sists of those algebras A for which the Alder—Strassen Bound is sharp, i.e., R(A) = 2dim A—t is the number of maximal twosided ideals in A. These algebras are called algebras of minimal rank. We determine all semisimple algebras of minimal rank over arbitrary fields and all algebras of minimal rank over algebraically closed fields. Received: January 12, 2000.     

Finite dimensional filters with non-linear drift IX Construction of finite dimensional estimation algebras of non-maximal rank

The idea of using estimation algebra to construct finite-dimensional nonlinear filters was first proposed by Brockett and Mitter independently. It has proven to be an invaluable tool in the study of nonlinear filtering problem. In 1983, Brockett proposed to classify all finite-dimensional estimation algebras. In this paper, we give the construction of finite-dimensional estimation algebras of non-maximal rank. These non-maximal rank finite-dimensional estimation algebras play an important role in Brockett's classification problem.     

A note on border rank

A closed condition for tensors of border rank ? r is given. Applied to the structural tensor <n, n, n,> of n × n matrix multiplication this criterion yields a $\text{3}\text{2}\text{n}{}^2\text{+}\text{1}\text{2}\text{n}\text{? 1}$ lower bound on its border rank.     

Approximation of almost solvable bilinear systems

The complexity of the Wei-Norman integration for a bilinear system can be reduced by approximating the associated Lie algebra by one of lower dimension. An algorithm is given for approximating a class of bilinear systems in this way in the case their Lie algebras are almost solvable.     

Decomposition of algebras over finite fields and number fields

We consider the boolean complexity of the decomposition of semi-simple algebras over finite fields and number fields.We present new polynomial time algorithms for the decomposition of semi-simple algebras over these fields. Our algorithms are somewhat simpler than previous algorithms, and provide parallel reductions from semi-simple decomposition to the factorization of polynomials. As a consequence we obtain efficient parallel algorithms for the decomposition of semi-simple algebras over small finite fields. We also present efficient sequential and parallel algorithms for the decomposition of a simple algebra from a basis and a primitive idempotent. These will be applied in a subsequent paper to obtain Las Vegas polynomial time algorithms for the decomposition of matrix algebras over and .     

On the rank of certain finite fields

In the present paper we shall show that the rank of the finite field regarded as an -algebra has one of the two values 2n or 2n+1 ifn satisfies 1/2q+1<n<1/2(m(q)–2). Herem(q) denotes the maximum number of -rational points of an algebraic curve of genus 2 over . Using results of Davenport-Hasse, Honda and Rück we shall give lower bounds form(q) which are close to the Hasse-Weil bound . For specialq we shall further show thatm(q) is equal to the Hasse-Weil bound.     

Classification of nilpotent lie algebras of dimension nine whose maximum abelian ideal is of dimension seven

The classification of Nilpotent Lie Algebras has been partially achieved up to dimension eight but this specific problem remained unsolved, since it required an enormous amount of calculations. Nowadays, with the aid of modern computers, it can be solved by designing the proper algorithms. The aim of this paper is to provide the results of the classification of Nilpotent Lie Algebras of dimension nine, whose maximum abelian ideal is of dimension seven.     

Theorems on the structure of finite dimensional estimation algebras

In this paper we proved several theorems concerning the structure of finite dimensional estimation algebras. In particular, under proper technical assumptions, we proved the following: (1) The observation of a filtering system must be linear if the estimation algebra is finite dimensional. (2) All elements of a finite dimensional estimation algebra belong to a special class of polynomial differential operators. (3) All finite dimensional estimation algebras are solvable.     

The complexity of homomorphisms and renamings for minimal unsatisfiable formulas

We investigate the complexity of deciding whether for minimal unsatisfiable formulas F and H there exists a variable renaming, a literal renaming or a homomorphism such that (F) = H. A variable renaming is a permutation of variables. A literal renaming is a permutation of variables which additionally replaces some of the variables by its complements. A homomorphism can be considered as a literal renaming which can map different literals to one literal.     

The complexity of homomorphisms and renamings for minimal unsatisfiable formulas

We investigate the complexity of deciding whether for minimal unsatisfiable formulas F and H there exists a variable renaming, a literal renaming or a homomorphism such that (F)=H. A variable renaming is a permutation of variables. A literal renaming is a permutation of variables which additionally replaces some of the variables by its complements. A homomorphism can be considered as a literal renaming which can map different literals to one literal.     

The logic of Peirce algebras

Peirce algebras combine sets, relations and various operations linking the two in a unifying setting. This paper offers a modal perspective on Peirce algebras. Using modal logic a characterization of the full Peirce algebras is given, as well as a finite axiomatization of their equational theory that uses so-called unorthodox derivation rules. In addition, the expressive power of Peirce algebras is analyzed through their connection with first-order logic, and the fragment of first-order logic corresponding to Peirce algebras is described in terms of bisimulations.     

Computation of bases of free modules over the Weyl algebras

A well-known result due to J.T. Stafford asserts that a stably free left module M over the Weyl algebras D=A_n(k) or B_n(k)–where k is a field of characteristic 0–with is free. The purpose of this paper is to present a new constructive proof of this result as well as an effective algorithm for the computation of bases of M. This algorithm, based on the new constructive proofs [Hillebrand, A., Schmale, W., 2001. Towards an effective version of a theorem of Stafford. J. Symbolic Comput. 32, 699–716; Leykin, A., 2004. Algorithmic proofs of two theorems of Stafford. J. Symbolic Comput. 38, 1535–1550] of J.T. Stafford’s result on the number of generators of left ideals of D, performs Gaussian elimination on the formal adjoint of the presentation matrix of M. We show that J.T. Stafford’s result is a particular case of a more general one asserting that a stably free left D-module M with is free, where denotes the stable rank of a ring D. This result is constructive if the stability of unimodular vectors with entries in D can be tested. Finally, an algorithm which computes the left projective dimension of a general left D-module M defined by means of a finite free resolution is presented. It allows us to check whether or not the left D-module M is stably free.     

Characterization of a subclass of finite-dimensional estimation algebras with maximal rank application to filtering

Finite-dimensional estimation Lie algebras play a crucial role in the study of finite-dimensional filters for partially observed stochastic process. When the dynamics noise is Gaussian we can characterize the so-called estimation Lie algebras with maximal rank in terms of the observation functions (necessarily affine) and the drift (necessarily a sum of a skew-symmetric linear term and a gradient vector field, with a functional relationship), under the assumption that the estimation algebra has one and only one operator of order greater or equal to two in any of its basis.     

The systems of primitive roots the degree and rank of prime numbers

Using the notions of the rank and the degree of a prime p≠2 relative to a residue class g(modp), where g is a positive integer with (g,p)= 1, we study the systems of primitive roots. This study leads to the understanding of the behavior of the discrete periodical signals whose values are the digits of the inverses of integers expressed in an arithmetic system with base g.     

A graph-theoretic characterization for the rank of the transfer matrix of a structured system

In this paper structured systems are considered and the generic rank of the transfer matrix of such systems is introduced. It is shown that this rank equals the maximum number of vertex disjoint paths from the input vertices to the output vertices in the graph that can be associated to the structured system. This maximum number of disjoint paths can be calculated using techniques from combinatorics. As an application a structural version of the well-known almost disturbance decoupling problem is proposed. The results in this paper were obtained while the author was affiliated with the Centre for Mathematics and Computer Science in Amsterdam, The Netherlands.     

The minimal average latency of multiconfigurable pipelines

It is shown that the average latencies of all sequences of optimal cycles through a fixed vertex in the state graph of a multiconfigurable pipeline have a common limit, provided that their initiation numbers are unbounded and approximate the same ratio of the underlying operations. This leads to a definition of the minimal average latency of a multiconfigurable pipeline.     

An algorithm to compute the Wedderburn decomposition of semisimple group algebras implemented in the GAP package wedderga

We present an algorithm to compute the Wedderburn decomposition of semisimple group algebras based on a computational approach of the Brauer–Witt theorem. The algorithm was implemented in the GAP package wedderga.