A new second-order Mehrotra-type predictor-corrector algorithm for SDO

In Zhang's recent works,a second-order Mehrotra-type predictor-corrector algorithm for linear optimization was extended to semidefinite optimization and derived that the algorithm for semidefinite optimization had O(n~(3/2)log(X~0)~T·S~0/ε) iteration complexity based on the NT direction as Newton search direction. In this paper, we extend the second-order Mehrotra-type predictor-corrector algorithm for linear optimization to semidefinite optimization and discuss the polynomial convergence of the algorithm by modifying the corrector direction and new iterates. It is proved that the iteration complexity is reduced to O(n~(3/2)log(X~0)~T·S~0/ε), which coincides with the currently best iteration bound of Mehrotra-type predictor-corrector algorithm for semidefinite optimization.     

A wide neighborhood arc-search interior-point algorithm for convex quadratic programming

In this paper, we propose an arc-search interior-point algorithm for convex quadratic programming with a wide neighborhood of the central path, which searches the optimizers along the ellipses that approximate the entire central path. The favorable polynomial complexity bound of the algorithm is obtained, namely O(nlog(( x~0)~TS~0/ε)) which is as good as the linear programming analogue. Finally, the numerical experiments show that the proposed algorithm is efficient.     

An algorithm for the spectral immunity of binary sequence with period 2<Superscript><Emphasis Type="Italic">n</Emphasis></Superscript>

To resist the fast algebraic attack and fast selective discrete Fourier transform attacks, spectral immunity of a sequence or a Boolean function was proposed. At the same time, an algorithm to compute the spectral immunity of the binary sequence with odd period N was presented, here N is a factor of 2 ⁿ ? 1, where n is an integer. The case is more complicated when the period is even. In this paper, we compute linear complexity of every orthogonal sequence of a given sequence using Chan-Games algorithm and k - error linear complexity algorithm. Then, an algorithm for spectral immunity of binary sequence with period N = 2 ⁿ is obtained. Furthermore, the time complexity of this algorithm is proved to be O(n).     

A quantum algorithm for the dihedral hidden subgroup problem based on lattice basis reduction algorithm

To optimize the algorithms for the dihedral hidden subgroup problem, we present a new algorithm based on lattice basis reduction algorithm. For n 〈 120, we reduce the dihedral hidden subgroup problem to shortest vector problem. A subroutine is given to get a transition quantum state by constructing a phase filter function, and then the measurement basis are derived based on the lattice basis reduction algorithm for solving low density subset sum problem. Finally, the parity of slope s is revealed by the measurement. This algorithm needs preparing mn quantum states, m qubits to store and O（n2） classical space, which is superior to existing algorithms.     

On the scalability of PSRS algorithm

In this paper, using the metric of iso-efficiency function [1]. we analyze the scalability of PSRS (Parallel Sorting by Regular Sample) algorithm [2] on two popular architectures (Mesh and Hypercube). The isoefficiency function of PSRS on 2-dimensional mesh withp processors reaches the lower bound $\Omega \left( {\sqrt p \cdot 2^{c\sqrt F } } \right)$ for that of sorting algorithms on this architecture. In this sense, we say, the scalability of PSRS is optimal on 2-dimensional mesh. The iso-efficiency function of PSRS on hypercube is equal to that of PSRS on 2-dimensional mesh. After changing the data exchanging scheme of PSRS, we get a new iso-efficiency functionO(log² p·p ^Ciogp), which is better than that of PSRS on 2-dimensional mesh So we say that hypercube is more suitable for PSRS than 2-dimensional mesh.     

Multi-pattern matching algorithm with wildcards based on bit-parallelism

Multi-pattern matching with wildcards is a problem of finding the occurrence of all patterns in a pattern set{p~1,---,p~k}in a given text t. If the percentage of wildcards in pattern set is not high,this problem can be solved using finite automata. We introduce a multi-pattern matching algorithm with a fixed number of wildcards to overcome the high percentage of the occurrence of wildcards in patterns. In our proposed method,patterns are matched as bit patterns using a sliding window approach. The window is a bit window that slides along the given text,matching against stored bit patterns. Matching process is executed using bit wise operations. The experimental results demonstrate that the percentage of wildcard occurrence does not affect the proposed algorithm's performance and the proposed algorithm is more efficient than the algorithms based on the fast Fourier transform. The proposed algorithm is simple to implement and runs efficiently in O(n+d(n/σ)(m/w))time,where n is text length,d is symbol distribution over k patterns,m is pattern length,and σ is alphabet size.     

Parallel (M−N)SVD algorithms on the SIMD computers

LetA bem byn matrix,M andN be positive definite matrices of orderm andn respectively. This paper presents an efficient method for computing (M?N) singular value decomposition ((M?N) SVD) ofA on a cube connected single instruction stream-multiple data stream (SIMD) parallel computer. This method is based on a one-sided orthogonalization algorithm due to Hestenes. On the cube connected SIMD parallel computer witho(n) processors, the (M?N)SVD of a matrixA requires a computation time ofo(m ³logm/n).     

一种基于矢量基2×2的二维FFT高效结构

提出了一种基于时间抽取原位计算的高效并行的二维矢量基2×2快速傅里叶变换的硬件实现结构.该算法结构将N×N点数据分解为4个独立存储的部分来实现矢量基2×2蝶形计算单元4个操作数的并行访问,仅用一个二维分裂基蝶形运算单元对这4块数据进行二维矢量基快速傅里叶变换,利用无冲突访问方法完成对存储器的并行访问.推导出了该算法硬件实现结构下的各存储器数据地址存取公式和旋转因子的产生方法,并利用CORDIC算法实现旋转因子的产生来减少存储器的使用.该算法对N×N点数据进行二维离散傅里叶变换处理的时间仅为(N2/2)(lb N-1)个时钟周期,与以往算法计算时间的比较结果表明了该设计的有效性.     

基于干扰对齐的设备到设备功率控制算法

为了使蜂窝网络系统中设备到设备(D2D)用户的速率总和最大,提出了一种基于干扰对齐(IA)的功率控制算法.该算法通过IA技术使得所有的D2D用户能够同时占用可使用的子载波;同时,控制每一个D2D用户在子载波上的功率,使所有D2D用户在对蜂窝用户(CU)产生的干扰小于干扰阈值的前提下,其速率和达到最大.仿真结果表明:与传统的基于频分多址(FDMA)的功率控制算法相比,本算法在干扰阈值为10 d Bm时,所得到的D2D用户的总速率和可提升约6 bit·S-1·Hz-1.     

Some algorithms for the error linear complexity of binary 2 n -periodic sequences

Based on the Games-Chan algorithm and StampMartin algorithm, this paper provides some new algorithms to compute the error linear complexity spectrum of binary 2n-periodic se-quences. These new algorithms are clearer and simpler than old algorithms, and they can quickly compute the error linear complexity spectrum of sequences according to different situations. We also discuss such algorithms and give some new results about linear complexity and error linear complexity of sequences.     

一种改进的Turbo码译码算法及其FPGA实现

为有效降低Turbo码在硬件实现时的译码复杂度并减少其存储资源消耗,将现有Turbo码译码算法中Log-MAP算法和Max-Log-MAP算法进行融合改进,提出一种适于并行计算的改进Max-Log-MAP算法,即在译码计算中间参数的过程中,只将具有多个输入变量的max*(·)运算简化为取最大值的max运算,而对具有2个输入变量的max*(·)运算进行精确计算. 仿真结果表明,改进Max-Log-MAP算法的复杂度可以接近Max-Log-MAP算法,而性能接近Log-MAP算法. 将采用新算法的Turbo码编译码器在现场可编程门阵列(FPGA)上实现,并应用于低轨卫星通信系统(LED)中的,能在保证Turbo编译码优异性能的同时,获得较低复杂度和较低资源消耗,有利于减小卫星手持通信终端的体积,降低功耗.      

An Improved Algorithm for k-Nearest-Neighbor Finding and Surface Normals Estimation

This paper is to improve the speed of k-nearest-neighbor search and put forward algorithms related to tangent plane estimation based on existing methods. Starting from the points cloud, the algorithm segments the whole data into many different small cubes in space, and the size of cube is related to the density of the points cloud. Considering the position of the point in the cube, the algorithm enlarges the area around the given point step by step until the k-nearest-neighbor is accomplished. The neighbor's least-squares tangent plane is estimated. In order to orient the planes, the k-nearest-neighbor is introduced into the problem of seeking the minimum spanning trees instead of searching the whole data. The research proved that the algorithms put forward in this paper were effective in processing data in short time and with high precision. The theory was useful for the practical application in reverse engineering and other areas related. Solution for finding k-nearest-neighbor problem, which still costs much time in present, was provided, and a propagation algorithm for orienting the planes was also discussed. The algorithm chose the orientation among the k-nearest-neighbor of the current point.     

基于MAC的动态回溯算法优化

针对基于MAC的动态回溯算法在求解约束满足问题时, 不仅需要大量空间存储删除解释, 而且回溯机制过于复杂, 对经典的删除解释及动态回溯算法的回溯机制进行优化, 优化后的动态回溯算法减少了存储删除解释的空间, 并可仅使用一次回溯操作返回到可能导致冲突的关键变量. 在最差情况下, 存储删除解释的空间复杂度由O(n²d)改进为O(nd+n²). 通过结合restart技术使优化后的动态回溯算法成为完备算法. 实验结果表明, 优化后的完备动态回溯算法在大部分问题求解中, 整体效率明显优于标准回溯算法.     

An efficient distributed algorithm for game tree search

This paper presents a distributed game tree search algorithm called DDS^*. Based on communication overhead, storage requirement, speed up, and other factors, the performance of algorithm DDS^* is analysed, and the number of nodes searched with SSS^* as well as a-b algorithm. The simulation test shows that DDS^* is an efficient and practical search algorithm.     

A Bayesian based quasi-analytical algorithm for retrieval of inherent optical properties from ocean color

The recently developed quasi-analytical algorithm （QAA） is a promising algorithm for deriving inherent optical properties from ocean color. Unlike the conventional semi-analytical algorithm, QAA does not need a priori knowledge of the spectral shape of chlorophyll absorption. However, several empirical relations, which may not be universally applicable and can result in low noise tolerance, are involved in QAA. In this study, the Bayesian inversion theory is introduced to improve the performance of QAA. In the estimation of total absorption coefficient at the reference wavelength, instead of empirical algorithms used in the QAA, the Bayesian approach is employed in combination with an optical model that uses separate parameters to account explicitly for the contribution of molecular and particle scatterings to remote sensing reflectance, a priori knowledge produced by the QAA, the Akaike＇s Bayesian information criterion （ABIC） for choosing the optimal regularization parameter, and genetic algorithms for global optimization. Coefficients at other wavelengths are then derived using an empirical estimate of particle backscattering spectral shape. When applied to a simulated dataset synthesized by IOCCG, the Bayesian algorithm outperforms QAA algorithm, especially in higher chlorophyll concentration waters. The root mean square errors （RMSEs） between the true and the derived α（440） and bb（440） are reduced from 0.918 and 0.039 m^-1 for QAA-555 to 0.367 and 0.023 m^-1 for Bayes-555, 0.205 and 0.007 m^-1 for QAA-640 to 0.092 and 0.005 m^-1 for Bayes-640, and 0.207 and 0.007 m^-1 for QAA-blending to 0.096 and 0.005 m^-1 for Bayes-blending. Results of noise sensitivity analysis show that the Bayesian algorithm is more robust than QAA.     

Present status and future prospect of design of Pt–cerium oxide electrodes for fuel cell applications

In the research field of proton exchange membrane fuel cells, the design of electrocatalytic activities on Pt-oxide promoter in the anode side has attracted attention for improvement of CO tolerance of Pt in anode side and a lowering of large over-potential loss of the oxygen reduction reaction on the cathode in the fuel cells. In the Pt-oxide promoter series, Pt–CeOx/C is one of the unique systems. It is because the unique behavior of CeOx such as electrochemical redox reaction between Ce3t and Ce4t in the anodic and cathodic reactions of fuel cell is observed. The present short review gives an overview of the recent works for improvement of the CO tolerance of Pt in the Pt–CeOx/C anodes and enhancement of the oxygen reduction reaction activity on Pt in the Pt–CeOx/C cathodes for fuel cell application. To show the design paradigm for fabrication of high quality Pt–CeOx/C electrodes, the authors re-introduced parts of our research results to highlight the important role of interface structure of Pt–CeOx based on the ultimate analysis results. The usefulness of the combined approach of microanalysis and the processing route design is presented.     

Remarks on the bounds for cryptanalysis of low private key RSA

Boneh and Durfee have developed a cryptanalytic algorithm on low private key RSA. The algorithm is based on lattice basis reduction and breaks RSA with private key d<N^0.292. Later on, an improved version by Blömer and May enhanced the efficiency, while reaching approximately this same upper bound. Unfortunately, in both the algorithms, there is a critical error in theoretical analysis, leading to the overestimated upper bound N^0.292. In this paper we present a more precise analytical model, with which the theoretical upper bound on d is modified to approximately d<N^0.277 for ordinary RSA systems with a 1024-bit public key (N,e).     

Classification by ALH-Fast Algorithm

The adaptive local hyperplane (ALH) algorithm is a very recently proposed classifier, which has been shown to perform better than many other benchmarking classifiers including support vector machine (SVM), K-nearest neighbor (KNN), linear discriminant analysis (LDA), and K-local hyperplane distance nearest neighbor (HKNN) algorithms. Although the ALH algorithm is well formulated and despite the fact that it performs well in practice, its scalability over a very large data set is limited due to the online distance computations associated with all training instances. In this paper, a novel algorithm, called ALH-Fast and obtained by combining the classification tree algorithm and the ALH, is proposed to reduce the computational load of the ALH algorithm. The experiment results on two large data sets show that the ALH-Fast algorithm is both much faster and more accurate than the ALH algorithm.     

锂离子电池荷电状态预测方法研究

针对电动汽车锂离子动力电池组能量管理中的荷电状态(SOC)预测问题,提出一种根据SOC及电流(SOC-I)计算库仑效率的方法,并建立电池SOC、充放电电流及充放电库仑效率的关系.以无迹卡尔曼滤波(UKF)算法为基础,采用自适应无迹卡尔曼滤波(AUKF)算法预测电池SOC,并将提出的库仑效率计算方法与UKF算法相结合构造了SOC-I-AUKF算法,该算法在预测过程中不断调整库仑效率、系统噪声协方差以及量测噪声协方差,以实现系统状态最优化预测.实验结果表明,SOC-I-AUKF算法有较好的SOC预测效果,与UKF算法相比,其SOC预测绝对误差、相对误差和平均误差水平都有显著提高.     

A time-space optimal parallel sorting on a hypercube

In this paper we discuss a parallel sorting algorithm on a hypercube. Its time complexity isO(n logn/p) +O(n). Here,P is the number of processors avaliable and n, the amount of items to be sorted. Take the problem of time-space optimization into consideration, whenP≤O(logn), this algorithm is both time-space optimal and cost optimization. But this means only speedup isO(p) and it is not linear speedup. Therefore, we further discuss relevant parallel efficiency problems.