New Applications and Algorithms that Involve the Kronecker Product

Kronecker产品有一个丰富的、非常令人愉快的代数，支持各种快速、优雅和实用的算法。科学计算的三个趋势表明，这种重要的矩阵运算在未来将发挥越来越大的作用。首先，克罗内克产品比比皆是的应用领域都在蓬勃发展。这些课程包括信号处理、图像处理、半定编程和量子计算。其次，稀疏分解和Kronecker积被证明是研究快速线性变换的首选方法。研究人员采用了为快速傅立叶变换开发的Kronecker方法，并用它来构建令人兴奋的替代方法。第三，随着计算机变得更强大，研究人员更愿意考虑高维的问题，这导致了每当低维技术被“张量”在一起时，Kronecker产品就会出现。此外，Kronecker产品是跟踪内存层次结构中数据移动的有用方法，而内存层次结构是先进机器的标志。鉴于这些发展，本项目的目标是扩大Kronecker积在数值线性代数中的使用。第一步是研究最近的Kronecker产品问题，因为这一领域的进展将带来新的和有趣的预调节想法。已经确定了其他需要Kronecker乘积近似的应用，并需要许多新的方法。所有的算法工作都将最终产生MatLab和C++库。这项研究将提高Kronecker产品在整个矩阵计算领域的知名度，从而使研究人员更容易在他们的工作中发现Kronecker的“机会”。通过建立有效的Kronecker乘积算法的“基础设施”，以该操作为特色的应用程序将以更快的速度激增。

The Kronecker product has a rich and very pleasing algebra that supports a wide range of fast, elegant, and practical algorithms. Three trends in scientific computing suggest that this important matrix operation will have an increasingly greater role to play in the future. First, the application areas where Kronecker products abound are all thriving. These include signal processing, image processing, semidefinite programming, and quantum computing. Second, sparse factorizations and Kronecker products are proving to be the preferred way to look at fast linear transforms. Researchers have taken the Kronecker methodology as developed for the fast Fourier transform and used it to build exciting alternatives. Third, as computers get more powerful, researchers are more willing to entertain problems of high dimension and this leads to Kronecker products whenever low-dimension techniques are "tensored" together. Moreover, Kronecker products are a useful way to keep track of data motion in memory hierarchies that are the hallmark of advanced machines. In light of these developments, the goal of this project is to widen the use of the Kronecker product in numerical linear algebra. The first step is to study the nearest Kronecker product problem because progress in this area will lead to new and interesting ideas for preconditioners. Other applications that require Kronecker product approximations have been identified and many new methods are called for. All of the algorithmic work will culminate in production of Matlab and C++ libraries. The research will heighten the profile of the Kronecker product throughout the field of matrix computations and thereby make it easier for researchers to spot Kronecker "opportunities" in their work. By building an "infrastructure" of effective Kronecker-product algorithms, applications that feature the operation will proliferate at an even greater rate.