Continuous-time orbit problems are decidable in polynomial-time

We place the continuous-time orbit problem in P$\mathsf{P}$, sharpening the decidability result shown by Hainry [7].     

针对LBlock算法的踪迹驱动Cache攻击

LBlock是一种轻量级分组密码算法,其由于优秀的软硬件实现性能而备受关注。目前针对LBlock的安全性研究多侧重于抵御传统的数学攻击。缓存( Cache)攻击作为一种旁路攻击技术,已经被证实对密码算法的工程实现具有实际威胁,其中踪迹驱动Cache攻击分析所需样本少、分析效率高。为此,根据LBlock的算法结构及密钥输入特点,利用访问Cache过程中密码泄露的旁路信息,给出针对LBlock算法的踪迹驱动Cache攻击。分析结果表明,该攻击选择106个明文,经过约27.71次离线加密时间即可成功恢复LBlock的全部密钥。与LBlock侧信道立方攻击和具有Feistel结构的DES算法踪迹驱动Cache攻击相比,其攻击效果更明显。     

高效动态存储再分配方案与实现

为提高大小和数量都不确定的数据动态存储的空间利用率和处理速度,针对常规系统动态存储分配存在的问题,提出一种高效的动态存储再分配方案。通过减少系统动态存储分配的执行次数,在有效提高存储空间利用率的同时,提高存储空间动态分配的速度,给出动态存储再分配方案的具体实现算法,用实际数据对其性能进行测试。测试结果表明,该方案能节省36％至75％的系统存储空间,分配速度提高了20至50倍。     

大规模定制环境下基于产品结构复杂度的工时定额制定研究

针对大规模定制环境下产品种类多、工时制定困难的特点,为了能够快速且准确获取产品工时,研究了产品结构复杂度与工时之间的关系,提出了一种基于产品结构复杂度的工时估算方法.综合考虑影响产品结构复杂度的各种因素后,针对决策结果的排序向量决定决策者权重,引入灰色关联理论,建立了产品结构复杂度计算模型.基于数据库中的工时信息,运用MATLAB软件进行编程确定产品结构复杂度和工时之间的函数关系.最后,以某企业产品加工工时估算实例,证明了所提出的估算方法的可行性.     

基于局部复杂度的环境遮挡

为了提高基于屏幕空间的环境遮挡算法(SSAO)的渲染速度,利用局部复杂度的帧间连续性,提出一种SSAO加速算法.首先为每个像素定义局部复杂度,其中局部复杂度相似的像素会有近似的环境遮挡(AO)值;在此基础上,利用帧间相关性,对于当前帧的像素p,若能在前几帧中找到与它有近似局部复杂度的某个像素,则可以直接复用前面帧的像素的AO值而无需重新计算;最后针对AO复用过程中产生的累积误差提出一种避免误差的方法.实验结果表明,在不影响效果的情况下,该算法可以将SSAO的渲染速度提高10%~40%.     

Coordinate descent with arbitrary sampling I: algorithms and complexity†

We study the problem of minimizing the sum of a smooth convex function and a convex block-separable regularizer and propose a new randomized coordinate descent method, which we call ALPHA. Our method at every iteration updates a random subset of coordinates, following an arbitrary distribution. No coordinate descent methods capable to handle an arbitrary sampling have been studied in the literature before for this problem. ALPHA is a very flexible algorithm: in special cases, it reduces to deterministic and randomized methods such as gradient descent, coordinate descent, parallel coordinate descent and distributed coordinate descent—both in nonaccelerated and accelerated variants. The variants with arbitrary (or importance) sampling are new. We provide a complexity analysis of ALPHA, from which we deduce as a direct corollary complexity bounds for its many variants, all matching or improving best known bounds.     

基于大规模MIMO网络的低复杂度块对角化算法

在多用户MIMO系统下行链路中,块对角化（Block diagonalization, BD）预编 码算法的和速率性能要优于匹配滤波算法（Matched filter, MF）和迫零算法（Zero forc i ng, ZF）。然而,传统的BD算法利用矩阵分解来构造除当前用户的其他所有用户信道的零空 间,需要O(N2)浮点运算次数（Float point operations, FLOPs）。当 基站的天线数N趋向于大规模时,BD算法计算复杂度巨大。本文 提出一种基于投影子方法构造其他用户合成信道的零空间的BD算法,该算法仅需O( N)FLOPs。仿真表明：同传统的BD算法相比,本文所提出的低复杂度BD算法显著地降低 了实现复杂度,而和速率性能损失微小,仍然优于MF和ZF,并且当N趋 向于大规模时,它的和速率性能趋向于传统的BD算法和SVD算法。     

A note about the complexity of minimizing Nesterov's smooth Chebyshev–Rosenbrock function

This short note considers and resolves the apparent contradiction between known worst-case complexity results for first- and second-order methods for solving unconstrained smooth nonconvex optimization problems and a recent note by Jarre [On Nesterov's smooth Chebyshev–Rosenbrock function, Optim. Methods Softw. (2011)] implying a very large lower bound on the number of iterations required to reach the solution's neighbourhood for a specific problem with variable dimension.     

Aesthetics and complexity in digital layout systems

Abstract

The layout of pages which carry information is the bread and butter of the graphic design profession. The rationale of what elements are chosen and where they are placed is based on tacit knowledge gained over a number of years of experience. The aesthetics associated with the overall finished design are often based on a style. Important elements of style are complexity and aesthetic value. In this paper I explore how various mathematical aesthetic functions can use complexity as an arousal enhancing or limiting mechanism in the application of layout designs.     

Pulse-order recursive method for inverse covariance matrix computation applied to space-time adaptive processing

The conventional space-time adaptive processing(STAP) method such as the typical sample matrix inversion(SMI)-based STAP method is difficult to implement for a practical system because intense computational complexity arises in calculating the inversion of a space-time covariance matrix directly.According to the block Hermitian matrix property of space-time covariance matrix,a new pulse-order recursive method is proposed in this paper to calculate the inverse covariance matrix for the STAP adaptive weight,which can reduce the computational complexity significantly.The proposed method requires initially calculating the inverse covariance matrix of the first pulse-order recursively based on the block Hermitian matrix property.In the following,the inversion of space-time covariance matrix is obtained recursively based on the previous pulse-order inverse covariance matrix.Next,the STAP adaptive weight is calculated based on the inversion space-time covariance matrix previously obtained.Compared with the conventional SMI-based STAP algorithms,the computational complexity of the proposed method is reduced to more than 50% for the same clutter suppression performance.This method can be applied to practical systems benefiting from small computational complexity and stable clutter suppression performance.