一种基二快速Hadamard变换的并行算法

作     者：秦书嘉 缪磊 崔龙 席宁 QIN Shujia;MIAO Lei;CUI Long;XI Ning

作者机构：中国科学院沈阳自动化研究所辽宁沈阳110016 中国科学院大学北京100049 密歇根州立大学 

出 版 物：《信息与控制》 (Information and Control)

年 卷 期：2016年第45卷第6期

页      面：707-712,721页

核心收录：

学科分类：0820[工学-石油与天然气工程] 0810[工学-信息与通信工程] 1205[管理学-图书情报与档案管理] 080202[工学-机械电子工程] 08[工学] 0804[工学-仪器科学与技术] 0802[工学-机械工程] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：国家自然科学基金资助项目(61102014) 国际热核聚变实验堆(ITER)计划资助项目(2012GB102005) 

主　　题：单像素相机 压缩感知 Hadamard变换 并行算法 

摘      要：快速Hadamard变换被广泛应用于信号与图像处理、通信系统、数字逻辑等领域中.当问题规模非常大时,快速Hadamard变换有可能不能满足计算时间的要求;这种情况下,算法并行化是一种行之有效的手段.本文以单像素相机的压缩感知图像复原为应用背景,利用基二快速Hadamard变换与快速傅里叶变换的结构相似性,提出一种通用的基二快速Hadamard变换的任务级并行算法,并用构造方式证明了该并行算法与串行算法计算结果之间的等价性.仿真表明对于小于2^(20)向量长度的问题规模以及并行子任务数少于2^(10)的情况,该并行算法对比串行算法的数值计算结果的欧氏距离平方误差小于10^(-18),佐证了并行算法的正确性.在PC平台通过多核CPU上POSIX线程实现的实验表明:在该特定平台和特定配置上对于220至225向量长度的问题规模并行计算加速比为1.33~1.42,证明了文中提出方法的可行性和有效性.