Fast Structured Matrix Computations: Tensor Rank and Cohn–Umans Method

We discuss a generalization of the Cohn–Umans method, a potent technique developed for studying the bilinear complexity of matrix multiplication by embedding matrices into an appropriate group algebra. We investigate how the Cohn–Umans method may be used for bilinear operations other than matrix multiplication, with algebras other than group algebras, and we relate it to Strassen’s tensor rank approach, the traditional framework for investigating bilinear complexity. To demonstrate the utility of the generalized method, we apply it to find the fastest algorithms for forming structured matrix–vector product, the basic operation underlying iterative algorithms for structured matrices. The structures we study include Toeplitz, Hankel, circulant, symmetric, skew-symmetric, f-circulant, block Toeplitz–Toeplitz block, triangular Toeplitz matrices, Toeplitz-plus-Hankel, sparse/banded/triangular. Except for the case of skew-symmetric matrices, for which we have only upper bounds, the algorithms derived using the generalized Cohn–Umans method in all other instances are the fastest possible in the sense of having minimum bilinear complexity. We also apply this framework to a few other bilinear operations including matrix–matrix, commutator, simultaneous matrix products, and briefly discuss the relation between tensor nuclear norm and numerical stability.     

Computing the matrix geometric mean: Riemannian versus Euclidean conditioning,implementation techniques,and a Riemannian BFGS method

This paper addresses the problem of computing the Riemannian center of mass of a collection of symmetric positive definite matrices. We show in detail that the condition number of the Riemannian Hessian of the underlying optimization problem is never very ill conditioned in practice, which explains why the Riemannian steepest descent approach has been observed to perform well. We also show theoretically and empirically that this property is not shared by the Euclidean Hessian. We then present a limited‐memory Riemannian BFGS method to handle this computational task. We also provide methods to produce efficient numerical representations of geometric objects that are required for Riemannian optimization methods on the manifold of symmetric positive definite matrices. Through empirical results and a computational complexity analysis, we demonstrate the robust behavior of the limited‐memory Riemannian BFGS method and the efficiency of our implementation when compared to state‐of‐the‐art algorithms.     

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.     

Randomized and quantum algorithms yield a speed-up for initial-value problems

Quantum algorithms and complexity have recently been studied not only for discrete, but also for some numerical problems. Most attention has been paid so far to the integration and approximation problems, for which a speed-up is shown in many important cases by quantum computers with respect to deterministic and randomized algorithms on a classical computer. In this paper, we deal with the randomized and quantum complexity of initial-value problems. For this nonlinear problem, we show that both randomized and quantum algorithms yield a speed-up over deterministic algorithms. Upper bounds on the complexity in the randomized and quantum settings are shown by constructing algorithms with a suitable cost, where the construction is based on integral information. Lower bounds result from the respective bounds for the integration problem.     

Decomposition for adjustable robust linear optimization subject to uncertainty polytope

We present in this paper a general decomposition framework to solve exactly adjustable robust linear optimization problems subject to polytope uncertainty. Our approach is based on replacing the polytope by the set of its extreme points and generating the extreme points on the fly within row generation or column-and-row generation algorithms. The novelty of our approach lies in formulating the separation problem as a feasibility problem instead of a max–min problem as done in recent works. Applying the Farkas lemma, we can reformulate the separation problem as a bilinear program, which is then linearized to obtained a mixed-integer linear programming formulation. We compare the two algorithms on a robust telecommunications network design under demand uncertainty and budgeted uncertainty polytope. Our results show that the relative performance of the algorithms depend on whether the budget is integer or fractional.     

有限维非退化可解李代数的顶点算子代数

构造相应于非退化可解李代数g的顶点算子代数分两步进行,首先构造顶点代数.本文是在已经得到的相应于非退化可解李代数g的顶点代数(Vg(l,0),Y(V,1)上构造顶点算子代数.定义了非退化可解李代数g的Casimir算子Ω,给出了在伴随表示下Ω作用在g上是0及相关性质,并应用Ω定义出Vg(l,0)中元素ω,证明了Vg(l,0)关于ω的顶点算子YV(ω,x)的系数构成一个Virasoro代数-模,还证明了ω满足顶点算子代数定义中Virasoro-向量的所有公理.从而证得(Vg(l,0),Yv,1,ω)是一个顶点算子代数.     

Maximization of A convex quadratic function under linear constraints

This paper addresses itself to the maximization of a convex quadratic function subject to linear constraints. We first prove the equivalence of this problem to the associated bilinear program. Next we apply the theory of bilinear programming developed in [9] to compute a local maximum and to generate a cutting plane which eliminates a region containing that local maximum. Then we develop an iterative procedure to improve a given cut by exploiting the symmetric structure of the bilinear program. This procedure either generates a point which is strictly better than the best local maximum found, or generates a cut which is deeper (usually much deeper) than Tui's cut. Finally the results of numerical experiments on small problems are reported.     

Randomized first order algorithms with applications to ℓ 1-minimization

In this paper we propose randomized first-order algorithms for solving bilinear saddle points problems. Our developments are motivated by the need for sublinear time algorithms to solve large-scale parametric bilinear saddle point problems where cheap online assessment of the solution quality is crucial. We present the theoretical efficiency estimates of our algorithms and discuss a number of applications, primarily to the problem of ? ₁ minimization arising in sparsity-oriented signal processing. We demonstrate, both theoretically and by numerical examples, that when seeking for medium-accuracy solutions of large-scale ? ₁ minimization problems, our randomized algorithms outperform significantly (and progressively as the sizes of the problem grow) the state-of-the art deterministic methods.     

The Graded Structure of Nondegenerate Meson Algebras

Meson algebras are involved in the wave equation of meson particles in the same way as Clifford algebras are involved in the Dirac wave equation of electrons. Here we improve and generalize the information already obtained about their structure and their representations, when the symmetric bilinear form under consideration is nondegenerate. We emphasize their parity grading. We calculate the center of these meson algebras, and the center of their even subalgebra. Finally we show that every nondegenerate meson algebra over a field contains a group isomorphic to the group of automorphisms of the symmetric bilinear form.      

实规范矩阵的特征值问题

实对称矩阵的特征值问题,无论是低阶稠密矩阵的全部特征值问题,或高阶稀疏矩阵的部分特征值问题,都已有许多有效的计算方法,迄今最重要的一些成果已总结在[5]中。本文利用规范矩阵的一些重要性质将对于Hermite矩阵(特别是对弥矩阵)特征值问题的一些有效算法推广到规范矩阵的特征值问题,由于对复规范阵的推广是简单的,而且实际上常遇到的是实矩阵(这时常要求只用实运算),因此我们着重讨论实规范矩阵的特征值问题。     

On inverse eigenvalue problems for block Toeplitz matrices with Toeplitz blocks

We propose an algorithm for solving the inverse eigenvalue problem for real symmetric block Toeplitz matrices with symmetric Toeplitz blocks. It is based upon an algorithm which has been used before by others to solve the inverse eigenvalue problem for general real symmetric matrices and also for Toeplitz matrices. First we expose the structure of the eigenvectors of the so-called generalized centrosymmetric matrices. Then we explore the properties of the eigenvectors to derive an efficient algorithm that is able to deliver a matrix with the required structure and spectrum. We have implemented our ideas in a Matlab code. Numerical results produced with this code are included.     

On systems of bilinear forms whose minimal division-free algorithms are all bilinear

In this paper we prove that for a certain class of systems of bilinear forms, all minimal division-free algorithms are essentially bilinear. This class includes systems for computing products in finite algebraic extension fields, and systems for computing the products of Toeplitz and Hankel matrices with vectors. Our results, together with the classification theorems of 10., 12., 169–180) completely describe all minimal division-free algorithms for computing these systems. We also prove, as an immediate consequence of our results, that the multiplicative complexity of the quaternion product over a real field is 8.     

群零模正则化问题的等价Lipschitz优化模型

针对群零模正则化问题, 从零模函数的变分刻画入手, 将其等价地表示为带有 互补约束的数学规划问题(简称MPCC问题), 然后证明将互补约束直接罚到MPCC的目标函数而得到的罚问题是MPCC问题的全局精确罚. 此精确罚问题的目标函数不仅在可行集上全局Lipschitz连续而且还具有满意的双线性结构, 为设计群零模正则化问题的序列凸松弛算法提供了满意的等价Lipschitz优化模型.     

A note on the Geronimus transformation and Sobolev orthogonal polynomials

In this note we recast the Geronimus transformation in the framework of polynomials orthogonal with respect to symmetric bilinear forms. We also show that the double Geronimus transformations lead to non-diagonal Sobolev type inner products.     

Single-machine scheduling problems with actual time-dependent and job-dependent learning effect

In this study, we introduce an actual time-dependent and job-dependent learning effect into single-machine scheduling problems. We show that the complexity results of the makespan minimization problem and the sum of weighted completion time minimization problem are all NP-hard. The complexity result of the maximum lateness minimization problem is NP-hard in the strong sense. We also provide three special cases which can be solved by polynomial time algorithms.     

Flat Nonunimodular Lorentzian Lie Algebras

A flat Lorentzian Lie algebra is a left symmetric algebra endowed with a symmetric bilinear form of signature (?, +,…, +) such that left multiplications are skew-symmetric. In geometrical terms, a flat Lorentzian Lie algebra is the Lie algebra of a Lie group with a left-invariant Lorentzian metric with vanishing curvature. In this article, we show that any flat nonunimodular Lorentzian Lie algebras can be obtained as a double extension of flat Riemannian Lie algebras. As an application, we give all flat nonunimodular Lorentzian Lie algebras up to dimension 4.     

Some results on the strength of relaxations of multilinear functions

We study approaches for obtaining convex relaxations of global optimization problems containing multilinear functions. Specifically, we compare the concave and convex envelopes of these functions with the relaxations that are obtained with a standard relaxation approach, due to McCormick. The standard approach reformulates the problem to contain only bilinear terms and then relaxes each term independently. We show that for a multilinear function having a single product term, this approach yields the convex and concave envelopes if the bounds on all variables are symmetric around zero. We then review and extend some results on conditions when the concave envelope of a multilinear function can be written as a sum of concave envelopes of its individual terms. Finally, for bilinear functions we prove that the difference between the concave upper bounding and convex lower bounding functions obtained from the McCormick relaxation approach is always within a constant of the difference between the concave and convex envelopes. These results, along with numerical examples we provide, give insight into how to construct strong relaxations of multilinear functions.     

Anisotropic Modules over Artinian Principal Ideal Rings

Let V be a finite-dimensional vector space over a field k, and let W be a 1-dimensional k-vector space. Let ?,?: V × V → W be a symmetric bilinear form. Then ?,? is called anisotropic if for all nonzero v ∈ V we have ? v, v ? ≠ 0. Motivated by a problem in algebraic number theory, we give a generalization of the concept of anisotropy to symmetric bilinear forms on finitely generated modules over artinian principal ideal rings. We will give many equivalent definitions of this concept of anisotropy. One of the definitions shows that a form is anisotropic if and only if certain forms on vector spaces are anisotropic. We will also discuss the concept of quasi-anisotropy of a symmetric bilinear form, which has no vector space analogue. Finally, we will discuss the radical root of a symmetric bilinear form, which does not have a vector space analogue either. All three concepts have applications in algebraic number theory.     

Design of space thrusters: a topology optimization problem solved via a Branch and Bound method

In this paper, an exact Branch and Bound Algorithm has been developed to solve a difficult global optimization problem concerning the design of space thrusters. This optimization problem is hard to solve mainly because the objective function to be minimized is implicit and must be computed by using a Finite Element method code. In a previous paper, we implement a method based on local search algorithms and we then proved that this problem is non convex yielding a strong dependency between the obtained local solution and the starting points. In this paper, by taking into account a monotonicity hypothesis that we validated numerically, we provide properties making it possible the computation of bounds. This yields the development of a topology optimization Branch and Bound code. Some numerical examples show the efficiency of this new approach.     

An elastodynamic Galerkin Boundary Element Formulation for semi-infinite domains in time-domain

The present work focuses on the problem of modelling wave propagation phenomena within a 3–d elastodynamic halfspace by use of a symmetric Galerkin Boundary Element formulation. Unfortunately, this formulation requires the evaluation of hypersingular integral kernels which are regularized by integration by parts. In Boundary Element Methods semi–infinite domains are commonly approximated in space by considering just a sufficiently large enough region. Applying this simple discretization to the symmetric formulation implies the evaluation of the hypersingular bilinear form on a truncated mesh which will fail due to the regularization approach. To overcome this drawback a methodology based on infinite elements is presented. The numerical tests show that this approach is promising for treating semi–infinite domains with a symmetric Galerkin scheme. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)