Quantum algorithm for neighborhood preserving embedding

Neighborhood preserving embedding (NPE) is an important linear dimensionality reduction technique that aims at preserving the local manifold structure. NPE contains three steps, i.e., finding the nearest neighbors of each data point, constructing the weight matrix, and obtaining the transformation matrix. Liang et al. proposed a variational quantum algorithm (VQA) for NPE [Phys. Rev. A 101 032323 (2020)]. The algorithm consists of three quantum sub-algorithms, corresponding to the three steps of NPE, and was expected to have an exponential speedup on the dimensionality n. However, the algorithm has two disadvantages: (i) It is not known how to efficiently obtain the input of the third sub-algorithm from the output of the second one. (ii) Its complexity cannot be rigorously analyzed because the third sub-algorithm in it is a VQA. In this paper, we propose a complete quantum algorithm for NPE, in which we redesign the three sub-algorithms and give a rigorous complexity analysis. It is shown that our algorithm can achieve a polynomial speedup on the number of data points m and an exponential speedup on the dimensionality n under certain conditions over the classical NPE algorithm, and achieve a significant speedup compared to Liang et al.'s algorithm even without considering the complexity of the VQA.     

全局优化问题的一个新的无参数填充函数

求全局最优化问题的填充函数算法被提出以来，参数的选取和调整一直是制约算法有效性的因素。如何在实际的计算过程中选取合适的参数，直接影响和决定了运算速度和效率。因此，构造不含参数的填充函数就显得极为重要。提出一个新的无参数的填充函数，对其理论性质进行了分析，并给出相应的填充函数算法，数值计算验证了算法的有效性。     

Performance guarantees of forward and reverse greedy algorithms for minimizing nonsupermodular nonsubmodular functions on a matroid

This letter studies the problem of minimizing increasing set functions, equivalently, maximizing decreasing set functions, over the base matroid. This setting has received great interest, since it generalizes several applied problems including actuator and sensor placement problems in control, task allocation problems, video summarization, and many others. We study two greedy heuristics, namely, the forward and reverse greedy. We provide two novel performance guarantees for the approximate solutions obtained by them depending on both submodularity ratio and curvature.     

白云石制备似立方体状方解石型碳酸钙晶体及其机理研究

以轻烧白云石粉、氯化铵和二氧化碳为原料,在未使用晶型控制剂的情况下,通过蒸氨-沉钙过程制备出了似立方体状碳酸钙。研究了反应温度、溶液中钙离子浓度、通气速率、搅拌速度以及陈化时间对碳酸钙中方解石相含量以及晶体形貌的影响,并探索了沉钙反应的晶型控制机理。结果表明,在反应温度40 ℃、钙离子浓度0.05 mol/L、通碳速率100 mL/min、搅拌速度400 r/min和陈化时间2 h的条件下,制备出形貌规整、粒径分布均匀的似立方体状碳酸钙,平均粒径为5~10 μm。该研究为提升白云石的使用价值、生产高附加价值的碳酸钙产品,以及提高白云石资源的利用率提供理论基础。     

粗糙表面之间接触热阻反问题研究

当两个固体表面相互接触时,由于接触面粗糙度的影响,界面间就形成了非一致接触,这种接触导致热流收缩,进而产生接触热阻. 目前的理论研究主要集中在正问题研究,对反问题的研究相对较少. 接触热阻反问题研究是通过研究部分边界温度、热流和部分测量点的温度来反演得到界面上的接触热阻. 反问题研究在很多工程领域都有应用,如航空航天、机械制造、微电子等,是工程中确定接触热阻一种快速有效的方法. 本文采用边界元法和共轭梯度法研究了二维空间随坐标变化的接触热阻反问题. 为了验证方法的准确性和可行性,假定在已知部分测量点温度和真实接触热阻的情况下,反演计算得到界面的温度和热流,进而得到接触热阻,并与真实接触热阻进行比较. 结果表明采用边界元法和共轭梯度法在无测量误差的情况下,可以准确反演获得界面的真实接触热阻. 若存在测量误差,反演计算结果对测量误差极其敏感,反演结果误差会由于测量误差的引入而被放大. 为处理这种不适定性, 采用最小二乘法对反演计算结果进行校正,结果表明采用最小二乘法能够避开反问题中一些偏离实际值较大的测量点,显著提高反演计算结果的准确性.      

基于Caputo导数的分数阶非线性振动系统响应计算

研究了含分数阶Caputo导数的非线性振动系统响应的数值计算方法。首先，由Caputo分数阶导数算子的叠加关系，得到含分数阶导数项非线性振动系统状态方程的标准形式。其次，基于Caputo导数与Riemann-Liouville导数和Grunwald-Letnikov导数间的关系，推导计算了Caputo导数的一般数值迭代格式。本文方法不要求状态方程中各分数阶导数阶数相等，弱化了已有算法中对分数阶导数阶数的限制，并可推广到多自由度的情形。随后，选择若干有解析解的算例验证了本文方法的正确性。最后，以多吸引子共存的分数阶Duffing振子系统为例，比较Caputo和GL两种算法所得结果，说明了用GL算法求解存在的问题。     

REBOUNDING OF GALILEAN CANNON FROM A RIGID WALL1)

研究了Galilean炮——即若干个直径递增的弹性球组成的球链---撞击刚性壁回弹的问题。采用三种力学模型：分离刚体的多次"弹性"碰撞、多刚体的接触碰撞、以及有限元模拟，对球链撞击问题进行了分析，旨在给出碰撞结束后末端小球的飞离速度与入射速度的比值。研究表明：球链碰撞反弹后将会散开，末端小球的飞离速度明显大于球链入射速度；当入射球链间存在间隙时，末端小球的速度增幅更加明显。通过实验展现了这种末端小球回弹速度增加的现象。     

Gear shifting multi-objective optimization to improve vehicle performance,fuel consumption,and engine emissions

In the present work, the Adaptive-Weight Genetic Algorithm was employed in order to determine the gear shifting strategies that allow an automobile to work in the best compromise among fuel consumption, engine emissions, and vehicle performance. For the assessment of each of the three objective functions, a simulation model based on engine data and on the well-established equations of the longitudinal dynamics was developed. The driving cycle chosen for the calculations was the FTP-75, which takes into account both cold and hot starts, meaning that the transient operation during the warm-up of the catalyst is also considered.     

Approximating total weighted completion time on identical parallel machines with precedence constraints and release dates

We present a $(2+2ln2+\epsilon )$-approximation algorithm for the classical nonpreemptive scheduling problem to minimize the total weighted completion time of jobs on identical parallel machines subject to release dates and precedence constraints, improving upon the previously best known 4-approximation algorithm from 1998. The result carries over to the more general problem with precedence delays and generalizes a recent result by Li (2017) for the problem without release dates or delays.     

求解矩阵方程AXB+CXD=F参数迭代法的最优参数分析

本文针对求矩阵方程AXB+CXD=F唯一解的参数迭代法，分析当矩阵A，B，C，D均是Hermite正（负）定矩阵时，迭代矩阵的特征值表达式，给出了最优参数的确定方法，并提出了相应的加速算法.