Direct sums of bilinear algorithms

We consider the bilinear complexity of certain sets of bilinear forms. We study a class of direct sums of bilinear forms. For this class of problems we show that the bilinear complexity of one direct sum is the sum of the bilinear complexities of the summands and that every minimal bilinear algorithm for computing the direct sums is a direct-sum algorithm. We also exhibit some sets of bilinear forms which belong to this class.     

Two criteria to check whether ideals are direct sums of cyclically presented modules

A famous theorem of commutative algebra due to I. M. Isaacs states that “if every prime ideal of R is principal, then every ideal of R is principal”. Therefore, a natural question of this sort is “whether the same is true if one weakens this condition and studies rings in which ideals are direct sums of cyclically presented modules?” The goal of this paper is to answer this question in the case R is a commutative local ring. We obtain an analogue of Isaacs's theorem. In fact, we give two criteria to check whether every ideal of a commutative local ring R is a direct sum of cyclically presented modules, it suffices to test only the prime ideals or structure of the maximal ideal of R. As a consequence, we obtain: if R is a commutative local ring such that every prime ideal of R is a direct sum of cyclically presented R-modules, then R is a Noetherian ring. Finally, we describe the ideal structure of commutative local rings in which every ideal of R is a direct sum of cyclically presented R-modules.     

Tight Bounds for Averaging Multi-Frequency Differential Inclusions,Applied to Control Systems

We present new tight bounds for averaging differential inclusions, which we apply to multi-frequency inclusions consisting of a sum of time periodic set-valued mappings. For this family of inclusions we establish a tight estimate of order O (??) on the approximation error. These results are then applied to control systems consisting of a sum of time-periodic functions.     

Algebraic modules and the Auslander-Reiten quiver

Recall that an algebraic module is a KG-module that satisfies a polynomial with integer coefficients, with addition and multiplication given by the direct sum and tensor product. In this article we prove that non-periodic algebraic modules are very rare, and that if the complexity of an algebraic module is at least 3, then it is the only algebraic module on its component of the (stable) Auslander-Reiten quiver. For dihedral 2-groups, we also show that there is at most one algebraic module on each component of the (stable) Auslander-Reiten quiver. We include a strong conjecture on the relationship between periodicity and algebraicity.     

Embedding and splitting ordinary differential equations in normal form

We introduce an embedding of real or complex n-dimensional space Kⁿ as an algebraic variety V which is determined by the action of a linear one-parameter group. Every analytic vector field on Kⁿ corresponds to some embedded vector field on V. For a symmetric vector field this embedded vector field splits into a reduced system and a direct sum of non-autonomous linear systems. Examples and applications are mostly concerned with Poincaré-Dulac normal forms. Embeddings provide a natural setting for perturbations of symmetric systems, in particular of systems in normal form up to some degree.     

Fast neighborhood search for the single machine total weighted tardiness problem

Most successful heuristics for solving 1||∑w_jT_j are based on swap moves. We present an algorithm which improves the complexity of searching the swap neighborhood from O(n³) to O(n²). We show that this result also improves the complexity of the recently developed dynasearch heuristics.     

Decompositions of modules lacking zero sums

A module over a semiring lacks zero sums (LZS) if it has the property that v +w = 0 implies v = 0 and w = 0. While modules over a ring never lack zero sums, this property always holds for modules over an idempotent semiring and related semirings, so arises for example in tropical mathematics.A direct sum decomposition theory is developed for direct summands (and complements) of LZS modules: The direct complement is unique, and the decomposition is unique up to refinement. Thus, every finitely generated “strongly projective” module is a finite direct sum of summands of R (assuming the mild assumption that 1 is a finite sum of orthogonal primitive idempotents of R). This leads to an analog of the socle of “upper bound” modules. Some of the results are presented more generally for weak complements and semi-complements. We conclude by examining the obstruction to the “upper bound” property in this context.     

Simplicity of lie module triple systems

We analyze how certain constructions of Lie module triple systems affect the structure theory, particularly simplicity. We are thus able to show that there is no upper bound on the number of summands in a direct sum decomposition of a simple Lie module triple system as a module for its inner derivation algebra.     

Single machine earliness and tardiness scheduling

We examine the problem of scheduling a given set of jobs on a single machine to minimize total early and tardy costs without considering machine idle time. We decompose the problem into two subproblems with a simpler structure. Then the lower bound of the problem is the sum of the lower bounds of two subproblems. A lower bound of each subproblem is obtained by Lagrangian relaxation. Rather than using the well-known subgradient optimization approach, we develop two efficient multiplier adjustment procedures with complexity O(nlog n) to solve two Lagrangian dual subproblems. A branch-and-bound algorithm based on the two efficient procedures is presented, and is used to solve problems with up to 50 jobs, hence doubling the size of problems that can be solved by existing branch-and-bound algorithms. We also propose a heuristic procedure based on the neighborhood search approach. The computational results for problems with up to 3 000 jobs show that the heuristic procedure performs much better than known heuristics for this problem in terms of both solution efficiency and quality. In addition, the results establish the effectiveness of the heuristic procedure in solving realistic problems to optimality or near optimality.     

On the Complexity of Sparse Elimination

Sparse elimination exploits the structure of a multivariate polynomial by considering its Newton polytope instead of its total degree. We concentrate on polynomial systems that generate zero-dimensional ideals. A monomial basis for the coordinate ring is defined from a mixed subdivision of the Minkowski sum of the Newton polytopes. We offer a new simple proof relying on the construction of a sparse resultant matrix, which leads to the computation of a multiplication map and all common zeros. The size of the monomial basis equals the mixed volume and its computation is equivalent to computing the mixed volume, so the latter is a measure of intrinsic complexity. On the other hand, our algorithms have worst-case complexity proportional to the volume of the Minkowski sum. In order to derive bounds in terms of the sparsity parameters, we establish new bounds on the Minkowski sum volume as a function of mixed volume. To this end, we prove a lower bound on mixed volume in terms of Euclidean volume which is of independent interest.     

On Integral Sum Graphs

A graph G is said to be an integral sum graph if its nodes can be given a labeling f with distinct integers, so that for any two distinct nodes u and v of G, uv is an edge of G if and only if f(u)+f(v) = f(w) for some node w in G. A node of G is called a saturated node if it is adjacent to every other node of G. We show that any integral sum graph which is not K₃ has at most two saturated nodes. We determine the structure for all integral sum graphs with exactly two saturated nodes, and give an upper bound for the number of edges of a connected integral sum graph with no saturated nodes. We introduce a method of identification on constructing new connected integral sum graphs from given integral sum graphs with a saturated node. Moreover, we show that every graph is an induced subgraph of a connected integral sum graph. Miscellaneous relative results are also presented.     

On integral sum graphs

A graph G is said to be an integral sum graph if its nodes can be given a labeling f with distinct integers, so that for any two distinct nodes u and v of G, uv is an edge of G if and only if f(u)+f(v)=f(w) for some node w in G. A node of G is called a saturated node if it is adjacent to every other node of G. We show that any integral sum graph which is not K₃ has at most two saturated nodes. We determine the structure for all integral sum graphs with exactly two saturated nodes, and give an upper bound for the number of edges of a connected integral sum graph with no saturated nodes. We introduce a method of identification on constructing new connected integral sum graphs from given integral sum graphs with a saturated node. Moreover, we show that every graph is an induced subgraph of a connected integral sum graph. Miscellaneous related results are also presented.     

Symmetric orthogonal filters and wavelets with linear-phase moments

In this paper we study symmetric orthogonal filters with linear-phase moments, which are of interest in wavelet analysis and its applications. We investigate relations and connections among the linear-phase moments, sum rules, and symmetry of an orthogonal filter. As one of the results, we show that if a real-valued orthogonal filter a is symmetric about a point, then a has sum rules of order m if and only if it has linear-phase moments of order 2m. These connections among the linear-phase moments, sum rules, and symmetry help us to reduce the computational complexity of constructing symmetric real-valued orthogonal filters, and to understand better symmetric complex-valued orthogonal filters with linear-phase moments. To illustrate the results in the paper, we provide many examples of univariate symmetric orthogonal filters with linear-phase moments. In particular, we obtain an example of symmetric real-valued 4-orthogonal filters whose associated orthogonal 4-refinable function lies in C²(R).     

A Monomial-by-Monomial Method for Computing Regular Solutions of Systems of Pseudo-Linear Equations

This paper deals with the local analysis of systems of pseudo-linear equations. We define regular solutions and use this as a unifying theoretical framework for discussing the structure and existence of regular solutions of various systems of linear functional equations. We then give a generic and flexible algorithm for the computation of a basis of regular solutions. We have implemented this algorithm in the computer algebra system Maple in order to provide novel functionality for solving systems of linear differential, difference and q-difference equations given in various input formats.     

Three-manifolds with Heegaard genus at most two represented by crystallisations with at most 42 vertices

It is known that every closed compact orientable 3-manifold M can be represented by a 4-edge-coloured 4-valent graph called a crystallisation of M. Casali and Grasselli proved that 3-manifolds of Heegaard genus g can be represented by crystallisations with a very simple structure which can be described by a 2(g+1)-tuple of non-negative integers. The sum of first g+1 integers is called complexity of the admissible 2(g+1)-tuple. If c is the complexity then the number of vertices of the associated graph is 2c. In the present paper we describe all prime 3-manifolds of Heegaard genus two described by 6-tuples of complexity at most 21.     

On quasiresolvent periodic abelian groups

This is a continuation of [1]. We introduce the concept of a primarily quasiresolvent periodic abelian group and describe primarily quasiresolvent and 1-quasiresolvent periodic abelian groups. We construct an example of a quasiresolvent but not primarily quasiresolvent periodic abelian group. For a direct sum of primary cyclic groups we obtain criteria for a group to be quasiresolvent, 1-quasiresolvent, and resolvent, and establish relations among them. We construct a set S of primes such that the direct sum of some cyclic groups of orders p ∈ S is not a quasiresolvent group.     

Sums of powers of the degrees of a graph

For a graph G and k a real number, we consider the sum of the kth powers of the degrees of the vertices of G. We present some general bounds on this sum for various values of k.     

Projectivity of Countable Direct Products

We show that if the direct product of countably many copies of a noetherian ring R is pure in a direct sum of finitely generated modules, then R satisfies the descending chain condition on two-sided ideals. This extends a recent result of Buchweitz and Flenner.     

On the complexity of the herding attack and some related attacks on hash functions

In this article, we analyze the complexity of the construction of the 2 ^k -diamond structure proposed by Kelsey and Kohno (LNCS, Vol 4004, pp 183–200, 2006). We point out a flaw in their analysis and show that their construction may not produce the desired diamond structure. We then give a more rigorous and detailed complexity analysis of the construction of a diamond structure. For this, we appeal to random graph theory (in particular, to the theory of random intersection graphs), which allows us to determine sharp necessary and sufficient conditions for the message complexity (i.e., the number of hash computations required to build the required structure). We also analyze the computational complexity for constructing a diamond structure, which has not been previously studied in the literature. Finally, we study the impact of our analysis on herding and other attacks that use the diamond structure as a subroutine. Precisely, our results shows the following:

1. The message complexity for the construction of a diamond structure is ${\sqrt{k}}$ times more than the amount previously stated in literature.

1. The time complexity is n times the message complexity, where n is the size of hash value.

Due to the above two results, the herding attack (Kelsey and Kohno, LNCS, Vol 4004, pp 183–200, 2006) and the second preimage attack (Andreeva et?al., LNCS, Vol 4965, pp 270–288, 2008) on iterated hash functions have increased complexity. We also show that the message complexity of herding and second preimage attacks on “hash twice” is n times the complexity claimed by Andreeva et?al. (LNCS, Vol 5867, pp 393–414, 2009), by giving a more detailed analysis of the attack.     

Split Malcev algebras

We study the structure of split Malcev algebras of arbitrary dimension over an algebraically closed field of characteristic zero. We show that any such algebras M is of the form $M={\mathcal U} +\sum_{j}I_{j}$ with ${\mathcal U}$ a subspace of the abelian Malcev subalgebra H and any I _j a well described ideal of M satisfying [I _j ,I _k ]?=?0 if j????k. Under certain conditions, the simplicity of M is characterized and it is shown that M is the direct sum of a semisimple split Lie algebra and a direct sum of simple non-Lie Malcev algebras.