首页> 外文期刊>ACM Transactions on Computational Theory >An Omega((n log n)/R) Lower Bound for Fourier Transform Computation in the R-Well Conditioned Model
【24h】

An Omega((n log n)/R) Lower Bound for Fourier Transform Computation in the R-Well Conditioned Model

机译:R-Well条件模型中傅里叶变换计算的Omega((n log n)/ R)下界

获取原文
获取原文并翻译 | 示例

摘要

Obtaining a nontrivial (superlinear) lower bound for computation of the Fourier transform in the linear circuit model has been a long-standing open problem for more than 40 years. An early result by Morgenstern from 1973, provides an Ω(n log n) lower bound for the unnormalized Fourier transform when the constants used in the computation are bounded. The proof uses a potential function related to a determinant. That result does not explain why the normalized Fourier transform (of unit determinant) should be difficult to compute in the same model. Hence, it is not scale insensitive. More recently, Ailon [2013] showed that if only unitary 2-by-2 gates are used, and additionally no extra memory is allowed, then the normalized Fourier transform requires Ω(n log n) steps. This rather limited result is also sensitive to scaling, but highlights the complexity inherent in the Fourier transform arising from introducing entropy, unlike, say, the identity matrix (which is as complex as the Fourier transform using Morgenstern's arguments, under proper scaling). This work improves on Ailon [2013] in two ways: First, we eliminate the scaling restriction and provide a lower bound for computing any scaling of the Fourier transform. Second, we allow the computational model to use extra memory. Our restriction is that the composition of all gates up to any point must be a well- conditioned linear transformation. The lower bound is Ω(R~(-1) n log n), where R is the uniform condition number. Well-conditioned is a natural requirement for algorithms accurately computing linear transformations on machine architectures of bounded word size. Hence, this result can be seen as a tradeoff between speed and accuracy. The main technical contribution is an extension of matrix entropy used in Ailon [2013] for unitary matrices to a potential function computable for any invertible matrix, using "quasi-entropy" of "quasi-probabilities."
机译:在线性电路模型中获得用于计算傅立叶变换的非平凡(超线性)下限一直是一个长期存在的开放问题,已有40多年的历史了。 Morgenstern于1973年的早期结果为计算中使用的常数有界时,为未规范化的Fourier变换提供了Ω(n log n)下界。证明使用与行列式相关的潜在函数。该结果不能解释为什么在同一模型中很难计算归一化傅立叶变换(单位行列式)。因此,它对规模不敏感。最近,Ailon [2013]表明,如果仅使用单一的2×2门,并且另外不允许额外的存储空间,则规范化的Fourier变换需要Ω(n log n)步。这个相当有限的结果对缩放也很敏感,但是突出了由于引入了熵而引起的傅立叶变换固有的复杂性,不像恒等矩阵(在适当的缩放下,它与使用Morgenstern的傅立叶变换一样复杂)。这项工作在Ailon [2013]上有两个方面的改进:首先,我们消除了缩放限制,并为计算傅立叶变换的任何缩放提供了下限。其次,我们允许计算模型使用额外的内存。我们的限制是,直到任何点的所有门的组成必须是条件良好的线性变换。下限是Ω(R〜(-1)n log n),其中R是统一条件数。对于在边界字大小的机器体系结构上精确计算线性变换的算法,良好的条件是自然的要求。因此,该结果可以看作是速度和精度之间的折衷。主要技术贡献是使用“拟概率”的“拟熵”将Ailon [2013]中用于unit矩阵的矩阵熵扩展到可计算为任何可逆矩阵的势函数。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号