Python中的高效线性变换框架Fastmat

=·∈== −∈软件X 18（2022）101013原始软件出版物fastmat：Python中的高效线性变换克里斯托弗·W·瓦格纳，塞巴斯蒂安·森佩尔，扬·基希霍夫德国伊尔梅瑙工业大学电子测量与信号处理（EMS）研究组ar t i cl e i nf o文章历史记录：收到2021年2022年2月7日收到修订版，2022年保留字：线性变换线性代数无矩阵压缩感知a b st ra ct科学计算需要处理大型线性模型，这些模型通常由结构化矩阵组成。随着模型大小的增加，密集表示很快变得无法计算或存储。无矩阵实现适合于以额外的实现开销为代价来缓解这个问题，当应用于实际研究问题时，这会使研究和开发工作复杂化数月。Fastmat是一个通过提供易于使用的抽象模型来处理大型结构化矩阵的框架。它允许以数学直观的方式表达无矩阵线性算子，同时保留其在计算性能和内存效率方面的优势内置的分层单元测试系统提高了调试效率，运行时执行路径优化提高了高度结构化运算符的性能。该架构完成了一个接口的抽象描述算法，适用于这种无矩阵的线性算子，同时保持清晰的分离，其各自的实现水平。Fastmat实现了在实现代码和给定问题的实际数学符号之间建立密切关系，促进了可读，可移植和可重用的科学代码。©2022作者（S）。由爱思唯尔公司出版这是CC BY许可下的开放获取文章（http://creativecommons.org/licenses/by/4.0/）中找到。代码元数据当前代码版本v0.2用于此代码版本的代码/存储库的永久链接https://github.com/ElsevierSoftwareX/SOFTX-D-21-00172Code Ocean compute capsule法律代码许可证Apache许可证2.0使用git的代码版本控制系统使用Python、Cython的软件代码语言、工具和服务编译要求、操作环境依赖性Numpy、Scipy、Cython、一些C-Builder（如果可用）开发人员文档/手册链接https://fastmat.readthedocs.io/en/latest/问题支持电子邮件sebastian.semper.tu-ilmenau.dechristoph. tu-ilmenau.de1. 动机和意义线性变换是应用数学、物理学、工程学和数据科学的基石之一在有限维向量空间的情况下，线性映射由矩阵表示，该矩阵编码如何使用图像空间的坐标来将周期性离散信号变换到相应的频域中，并且在频谱分析、雷达、阵列处理等方面也有大量应用。给定Cn中的正则标准基，相应的矩阵元素表示为[]n[（− <$2π ）] n表示另一个向量空间的所有基向量的图像然而，在许多应用中，线性映射并不一致。F=fi，k i，k=1=√expn·i·ki，k=1、（1）完全任意的，但表现出一些结构，往往源于物理模型[1，2]，自然过程的描述[3，4]或来自侧面约束的假设[5，6]。一个突出的例子是n∈N阶的离散傅里叶变换（DFT），*通讯作者。电子邮件地址：christoph. tu-ilmenau.de（Christoph W. Wagner）。https://doi.org/10.1016/j.softx.2022.101013其中，1。 我们可以看到，傅立叶矩阵F Cn×n 是高度结构化，没有自由度，因为所涉及的向量空间的大小已经完全定义了它的元素。为了实际执行线性映射m，这意味着在给定的输入向量x处对其求值以获得其图像ym（x），简单地计算yMx，如果MCm×n 是矩阵对线性映射m进行编码。一般来说，这是完成2352-7110/©2022作者。 由Elsevier B.V.出版。这是一篇开放获取的文章，使用CC BY许可证（http://creativecommons.org/licenses/by/4.0/）。可在ScienceDirect上获得目录列表SoftwareX期刊主页：www.elsevier.com/locate/softx克里斯托弗·W· 瓦格纳，塞巴斯蒂安·森佩尔，扬·基希霍夫软件X 18（2022）1010132⎦O·O=·：×→我通过使用M∑n产品，结构张量或块矩阵的展开）进一步提供了组合现有算子以抽象地构造复杂线性映射的能力，同时利用y=[yi]i=1=0j=1mi，j·xji=1=M·x。（二）一路上享受着无矩阵的好处。用户可以从广泛的内置矩阵（见图1）中进行选择，或者决定实施-注意，该公式需要计算复杂度为（n m），在运行时间和内存消耗方面回到我们的DFT例子，而不是简单地应用（2）字面上，应该使用快速傅立叶变换（FFT）[7]，以计算运行时复杂度（nlogn）的y F xFFT通过将DFT矩阵分解成较小的所谓的蝶形结构来利用结构冗余，这取决于变换大小及其素因子分解。这种冗余减少是实现实际应用的关键现代信号处理存在专用的和高度优化的库[7-特别是因为设计数值稳定的算法远非微不足道，这种抽象库通常被认为是高度可信的。因此，FFT通常被认为是DFT的频谱分析的主要选择对于许多这样的我们进一步将正变换φM：Cn→Cn定义为x→φM（x）=m（x）=Mx（3）以及后向变换βM：Cn→Cn为x→βM（x）=MHx，（4）其中MH表示矩阵M的厄米特转置。为了推导出处理（更复杂的）无矩阵表示的重要含义，让我们考虑具有向量c∈Cn的循环卷积，其通常实现为y=ifft（fft（c）ifft（x）），（5）哪里CnCnCn 执 行 Cn 中 两 个 向 量 的 逐 点 乘 法 （ 即Hadamard乘积）。我们现在可以看到，这两种表示开始出现分歧（在符号和程序代码中），这使得在理论层面上更难处理，并使两种表示保持同步。作为结果，实现错误的风险增加，研究人员被混淆（“膨胀”）的代码和各种维护问题分散了注意力2. 软件描述我们的软件提供了一个面向对象的编程接口矩阵自由的线性算子，紧密联系的结果，ING应用程序代码，其相应的数学nota和灰。独特的矩阵类应用程序编程接口（API）抽象任何（内部）矩阵的自由表示，在这种形式，他们可以像密集表示（外部）。二元和一元运算符（如使用fastmat用于快速评估数值精度、类性能或运行时执行路径优化。最后，Matrix-class- API由Algorithm-API补充，用于实现利用矩阵运算符的（信号处理）算法.2.1. 广义无矩阵表示每个线性变换都可以用矩阵（或矩阵的相互作用）以其稠密或无矩阵表示来描述。Matrix基类实现了一个通用的、结构独立的基本API，可以使用面向对象编程（OOP）原则从该API派生出更具体的类实现。因此，用户可以轻松地选择性地扩展现有的Matrix类，而只需实现新的功能，因为新类默认继承其父类的所有结构。这是可能的，因为类API在内部没有对线性变换做任何结构性假设.因此，我们的架构反映了从没有结构的假设（矩阵基类）的路径，更多的约束，更少的一般性和更高的效率（继承类）的方式，是完全透明的用户，这促进了代码的可移植性和重用。给定矩阵M的许多性质也可以从等式1中的前向和后向变换计算。（3）和（4）。例如，单个矩阵元素mi， j可以经由eTφM（ej）访问，独立于M或φM。Matrix基类提供了大量这样的通用量和属性的通用实现（见表1），这也得益于在一个专门的类中重载φ和β类API的所有属性和方法都被一些入门级接口代码包装，这些代码确保输入的健全性并提供扩展功能，例如运行时执行优化（参见附录B）。尽管如此，该机制确保用户可以覆盖他们的中央计算代码，而不必考虑不破坏此接口代码（参见附录C）。 根据定义，所有Matrix实例及其实例化参数都被认为是不可变的，因为这提供了允许预计算和缓存静态结果而不影响运行时一致性的巨大好处。后者由相应的通用属性的类API接口代码透明地这些机制的一个很好的例子是循环类，它实现了（5）中给出的计算。 由于c准确地定义了循环矩阵，因此在实例化期间完成预计算fft（c），然后在每个子集中重用其结果。quent调用到φ和β。作为整体架构哲学的体现，循环矩阵也不是通过以封闭形式分解（5）来实现的，而是通过将其定义为三个矩阵的乘积：共轭和转置傅立叶矩阵，对角矩阵和另一个傅立叶矩阵。考虑到我们已经正确地实现了Product、Fourier和Diag类，我们可以依靠它们作为循环定义的抽象层，其整体效率与封闭形式实现相当。一个广泛的运营商提供了快速垫开箱即用（见图。（1）经常互相参照。因此，fastmat的代码也与数学符号非常相似，而运行时和内存性能则受益于类架构中任何地方的无矩阵实现。克里斯托弗·W· 瓦格纳，塞巴斯蒂安·森佩尔，扬·基希霍夫软件X 18（2022）1010133图1.一、 fastmat类的列表，按基本和复合类型分组。为了能够依赖于单个操作符的正确性（特别是当它们彼此紧密交互时），fastmat提供了一种灵活的单元测试机制，该机制能够在运行时为任何fastmat类实现（包括用户定义的实现）运行细粒度的自动化测试。 即使是细微的实现错误深深植根于一个复杂的网络分层矩阵的自由运营商可以迅速确定使用元测试结果的代数分析。有关详细信息，请参阅软件包文档。总之，对于某些类型的复合运算符，它们各自的前向和后向变换本身可以单独从它们的运算符项的各自变换来描述。即使通过多层结构抽象，结构知识也被完全保留，并建立了fastmat驱动的代码与其使用数学符号的理论计算描述之间的密切关系，满足fastmat2.2. 无矩阵算法表示在纯矩阵的基础上，我们还提供了算法基类，它可以方便地将Matrix实例用于更复杂的例程，这些例程使用依赖于fastmat Matrix类API的线性变换这提供了一些显著的优点：首先，算法实现本身对于它所采用的底层矩阵的实际结构是完全不可知的作为一个直接的结果，任何矩阵实例，利用结构知识的效率，也将其利益传递给任何算法，它是采用。其次，Algorithm baseclass提供了一种方法，可以轻松地为各种目的建立用户回调，从而可以在运行时轻松地检查，调整或覆盖算法的某些方面，例如中断条件，步长，阈值或正则化参数的自定义确定。最后但同样重要的是，算法的代码结构是否克里斯托弗·W· 瓦格纳，塞巴斯蒂安·森佩尔，扬·基希霍夫软件X 18（2022）1010134×·····表1Matrix基类：属性、方法、重载和缓存。数学符号在其实现中更接近，特别是因为无矩阵表示所需的繁重工作不再扰乱算法的实现。大多数与过于复杂的代码单元相关的陷阱都可以通过fastmat的Matrix和Algorithm类API提供的代码整理来直接缓解。3. 说明性实例在建立了fastmat让我们考虑一下这个情况，其中仿真或测量分析中的某些线性映射是如此复杂和大，以致于选择密集表示经常导致运行时和/或存储器耗尽。尽管如此，由于它们与物理过程相关，它们的嵌入式结构产生了使用无矩阵表示的优化潜力。不幸的是，在科学代码中嵌入这样的表示通常会导致这样的情况，其中表示级代码优化使更高级别的应用程序代码变得混乱，增加了可读性和维护损失。这种解决方案的结果代码是高度特定的，导致可移植性问题并阻碍设计重用。通过应用fastmat原子类实现鼓励构建-使用共享库和API还可以作为数值单元测试的有用入口点，确保线性运算符满足规范，独立于应用程序级测试。结合起来，这些效应鼓励使用无矩阵方法，而不是出于对尝试机会成本的恐惧而坚持使用表现不佳的密集表示3.1. 定义自定义无矩阵运算符和算法在3.2节中深入研究高维物理建模的完整示例之前，我们将使用fastmat快速实现形状为N M的1矩阵的无矩阵实现，定义为使其密集表示的每个标量元素等于1。选择一个合适的基线类来继承，可以为新类节省大量的实现工作，新类很可能是任何其他Matrix类，带有一些参数化。 对于我们的例子，Matrix基类已经很适合了。新类的一般行为是通过重写方法_forward（）和_backward（）定义的，对应于 φ和β。必须指定init（）方法，该方法执行预计算（如果需要），并通过直接调用self.initProperties（（）中选择。由于一般矩阵基础-类实现之后，类就完成了（请参见清单1）。如果已知的话，可以通过重载特定的类属性和方法来添加进一步的优化（参见附录C）。本节的其余部分将简要概述如何使用fastmat测试，基准和校准系统的新类。 测试子系统设计用于对特定类进行数值精度的单元测试，需要定义两个方法：reference（）方法应该返回一个密集的引用数组进行比较，而_getTest（）必须返回测 试 用 例 生 成 器 的 有 效 配 置 。 为 了 使 校 准 功 能 可 用 ，_getComplexity（）必须实现一个模型，用于返回φ和β的相对复杂度估计值，最后，必须通过声明_getBenchmark（）来配置运行时基准，以便返回有效的基准配置。声明了这四个方法后，fastmat的所有特性现在都可以用于新定义的类。要使用运行时执行路径优化（参见附录B），可以从磁盘加载预先存在的校准数据，或者在运行时（在实例化之前）通过调用fastmat.core.calibrateClass（·）生成校准数据。1进口numpy，fastmat23类1（快速垫。矩阵）：4'''一个简单的1-矩阵实现'''56definit（self，nums，numCols）：7'''初始化fastmat类API并定义形状'''8自我。_initProperties（nums，numCols，numpy.int8）910def_forward（self，arrX）：11'''定义正向变换'''12返回numpy。resize（13numpy. sum（arrX，axis=0，keepdims=True），14（自我。数字，arrX。形状[1]）第十五章）1617def_backward（self，arrX）：18“”定义反向变换“”19返回numpy。resize（20块。sum（arrX，axis=0，keepdims=True），21（自我。numCols，arrX. 形状[1]）第二十二章）2324#需要定义的其他方法.25#- Testing：reference（），_getTest（）26###-校准：_getComplexity（），_getBenchmark（）27##实例化并使用新类29N，M=4，5; O=1（N，M）30xf=numpy。随机randn（M）;xb=numpy. 随机randn（N）31print（xf，'\n'，O*xf）;print（xb，'\n'，O.H*xb）清单1：1-Matrix的无矩阵实现的最小工作示例克里斯托弗·W· 瓦格纳，塞巴斯蒂安·森佩尔，扬·基希霍夫软件X 18（2022）1010135⊗P∈∈∑=||∥ ∥∈（）下一页：→（）下一页∈1- -232N3−12N2−1X2、1i，j=1现在，考虑单个Hi，j，由于其结构，其表示2D非循环卷积。这样的卷积可以通过较大的循环卷积和适当的输入零填充来实现。抛开技术细节，我们可以证明，Hi，j=P（（F2N−1<$F2N−1）·diag（hi，j）·（FH<$FH））， （7）图二. 传感器路径和测量位置。3.2. 超声无损检测超声波作为一种非破坏性的模态被广泛应用于制造、医学或维修等领域，以表征被测物体的内部。在无损检测中，人们还对检测和表征样品内可能的缺陷而不对物体造成任何损坏或改变感兴趣。下面，我们总结了最近使用超声无损检测[11]对缺陷进行3D重建的研究实例，特别关注其使用无矩阵方法和所提出的包fastmat的实现。一个换能器，发射超声波脉冲到样品中，沿着预定的轨迹移动以收集测量数据。在每个位置，我们通过插入已知波形并记录由于声阻抗的变化而在材料边界处产生的回波来拍摄快照。这个过程，如图2所示，创建一个合成孔径，这使我们能够恢复（以前未知的）位置，这种快速阻抗变化的研究介质。这些通常表示感兴趣的区域，我们的目标是从测量中提取。为了制定一个易于处理的参数估计问题，我们首先介绍了一个线性模型，该模型将编码可能的缺陷位置的矢量映射到由换能器捕获的可能的观察结果上。一般来说，这读起来像b=H·x+n，（6）其中b，xCn和HCn×n.在这个等式中，b是从图1中的传感器获得的测量值。二、矩阵H模拟了我们对发生在介质：如果我们插入脉冲波形，这些脉冲会被可能的缺陷反射，并且可以在记录的回波中看到。基于这个模型，x中的条目对应于对象中的某些位置。非零条目指示所述位置处的反射体或缺陷。因此，我们希望从测量值b中恢复x，以便推断这些位置。传感器在位于R3超平面中的规则2D网格上对齐的点上移动。在当我们为可能的缺陷位置引入精心选择的网格时的情况下，可以示出矩阵其中表示矩阵Kronecker乘积，diag（x）是以x作为对角线的对角矩阵，并且是负责正确补零的算子。为了实现该矩阵，可以使用Partial、Kron、Diag、fastmat的乘积、Hermitian和Fourier类。为了基于H和b进行x的估计，流行的方法是以下优化问题：min<$Hx−b<$2+τ<$x<$，（ 8）其中xp（ixip）（1/p）和τ >0是某个适当选择的超参数。有趣的是，有一些算法可以有效地近似解决（8）中的问题，仅仅基于近年来，人们发现正则化项τx1能够增强x的稀疏性，这对应于在测试中的样品内只有少数缺陷的假设。解决（8）中问题的一种方法是迭代收缩保持算法（ISTA）[12]，这是一系列具有不同性能的类似算法的基本灵感。然而，为了简单起见，我们提出了简单和基本的版本。为对于给定的初始估计x0Cn，我们简单地将下面的表达式代入，直到我们满足某个停止准则：xk+1=τsHH·（H·xk−b），其中τsCnCn是s > 0级的非线性函数（称为软阈值算子），其在x的大小上表现出线性运行时间。这意味着ISTA的最大计算工作量分别在于计算φH和βH投影，使其成为无矩阵实现的完美应用。对于ISTA，xk+1=τs βH（φH（xk）−b）.事实上，建模阶段和算法设计阶段彼此保持完全分离，使得H=[Hi j]N1，是一个分块矩阵，其中每个Hi，jC （ 2N2−1 ） （ 2N3−1 ） ×（2N2−1）（2N3−1）是一个2级Toeplitz矩阵。由于N1、N2和N3在缺陷位置的测量和重构期间与空间分辨率成比例，因为它们构成每个空间方向上的样本数量。稠密矩阵H很快就包含了大量的元素（N2（2N2 1）2（2N3 1）2）。由于这对于当前的系统存储器和计算资源来说太多了，我们必须采用涉及稠密矩阵H的变换的无矩阵实现，以保持在实际可行性的范围内。图三. 钢试样的稀疏恢复结果（俯视图）- 从 上 到 下 ：样品的示意图（顶视图），快速迭代收缩保持算法（FISTA）重建，正交匹配追踪（OMP）重建，通过合成孔径聚焦技术（SAFT）的波束形成。克里斯托弗·W· 瓦格纳，塞巴斯蒂安·森佩尔，扬·基希霍夫软件X 18（2022）1010136∈≪·∈==3712141621建议的工具箱作为研究工具非常有利相同的1无矩阵表示可以很容易地插入到其他suit-2能够使用所描述的类API的算法。4另一方面，我们也可以很容易地适应不同的5测量场景。压缩感知（CS）使用tech-6在稀疏信号恢复（SSR）中开发的用于估计8从压缩的测量信号参数。 如果我们ap-9将这种方法应用于缺陷检测问题，我们得到了10不同的观察模型，其读数为11b_n=n·H·x+n，（9）13其中，矩阵m×n使得mn，得到b=15包含比b少得多的测量。17在超声无损检测研究中，常见的18程序是使用测试规范-19比较成像算法人为引入目标缺陷的人此类缺陷为20通常由钻入22个孔标本的底部 图 3我们展示了23 的一些例子可能的重建这种缺陷的钢块。在这#或者你可以通过编码Eq。（7）从字面上看，FK = fastmat。Kron（快垫傅立叶（N2），快速垫。傅立叶（N3））H = fastmat。块（[[fastmat. 部分（FK*fastmat。Diag（h[i，j]）*FK. H，λ=vec_zeropad）对于范围（N1）中的j]for iinrange（N1）]）#或者你可以使用多层次Toeplitz类H = fastmat。区块（[[fastmat。Toeplitz（h[i，j]）对于范围（N1）中的j]for iinrange（N1）]）#在算法（8）中使用H的工作原理如下：导入fastmat算法alg=fastmat。算法ISTA（H，numLambda=numda）x= alg. 过程（b）在这种情况下，我们使用传感器通过从顶部测量样品来定位这些缺陷 见图 3中的三种不同算法的结果，即FISTA [12]，所述ISTA的轻微变体，OMP [13]（另一种非常适合无矩阵方法的稀疏执行算法）和SAFT，一种简单计算x βH（b）的波束成形方法。在我们的例子中，我们使用压缩N2N3许多单-在频域中独立地进行脉冲回波测量。这样我们就能i= blkdiag {Φ1，1，. . . ，ΦN1，N2}，其中，每个Φi，j是包含随机选择的傅立叶矩阵的N行和blkdiag算子以块对角结构排列矩阵。显然，测量矩阵具有无矩阵表示，同样地，产品也是可折叠的。如果我们简单地将新的测量值b和乘积bH代入已经讨论过的算法，如OMP，FISTA或ISTA，我们得到的结果如图4所示。在那里，我们仅使用来自每个原始收集的脉冲回波测量的单个傅立叶系数。为了证明我们的主张，即fastmat加强了代码-符号关系，我们展示了（7）的简化示例实现和（8）。该实例不仅表明建模和算法设计是完全分离的，还强调了适当抽象的模型的价值，通过轻松地添加压缩数据采集模型的设计。在交换模型（反映不同的采样方案或物理模型）和算法时，现在可以快速获得广泛的研究结果，同时重用大部分易于遵循的编程代码，这也与我们的数学公式非常相似。图 4. 使用20步的FISTA重建的俯视图和侧视图，nf1傅立叶系数和ΔH作为系统矩阵。清单2：Eq. （7）（给出两个变体）和Eq. （八）、4. 影响通过第2节中介绍的API设计，研究程序可以将低级优化从高级算法设计中抽象出来，而不会牺牲一般性能优化，从而大大提高了所产生代码的可读性、可扩展性和可移植性。由于类似于构造工具包的OOP方法，即使对于具有高性能优化潜力的复杂的无矩阵表示，也可以非常快速地实现线性映射。集成的测试功能通过将调试工作集中在所需的精确抽象级别上，大大减少了维护Concrete abstrac- tion将单个效率提升调整隔离到其特定架构级别。这改善了代码维护、接口清晰度和早期错误检测，一直到算法设计级别，加快了开发周期。所有这些功能使fastmat成为一种工具，可以提高研究人员，工程师或其团队的工作效率，这些团队经常需要处理大型结构模型和应用这些的算法。由于团队沟通是有限的（甚至已经被可用时间限制），这直接限制了可持续的问题复杂性和团队效率-我们的软件包有助于打破这种局面，使个别团队成员能够更好地了解他们的同行的问题，更快地交换意见，找到解决方案，提高他们的整体团队协作效率，为解决更复杂的问题做好准备。除了团队动态方面之外，最终的实施效率也足够接近最优值，因此，在剩余效率差距（源于实施的一般性）的情况下，低.因此，可以实现两个世界的最佳效果，因为不再必须为了速度而牺牲便利性（反之亦然）。最后，我们想参考应用fastmat的原始研究。在第3.2节中，我们展示了它的应用，克里斯托弗·W· 瓦格纳，塞巴斯蒂安·森佩尔，扬·基希霍夫软件X 18（2022）1010137从超声波测量中对缺陷进行基于CS的3D重建的问题，涉及密集但高度结构化的多维线性模型。fastmat通过将这些模型的内存占用从数PB减少到千兆字节范围来实现这项研究[11，15，16]。对于一种新型的基于CS的超宽带雷达架构，使用fastmat对整个信号采集硬件前端进行建模，以评估电路设计和信令选择对最终重建性能的影响[17]。 在机器学习领域，我们的软件包用于执行结构化核插值（SKI），以将高斯过程（GP）扩展到具有超过1亿个点的三维天气雷达数据集的大规模数据集[18]。我们的算法子系统的一个值得一提的应用，用于其高性能的有效秩1更新OMP实现，是在pygpc中，这是一个Python的灵敏度和不确定性分析工具箱[19]。5. 结论我们已经证明，通过精心设计的API，可以设计一个统一密集和无矩阵线性映射的架构，同时利用这两种方法的优势，并将它们之间的复杂性保持在最低限度。正如我们所展示的，这在所需的编写代码和设计过程方面都得到了简化构建一个具体的实现。从本质上讲，所描述的包允许更多地关注手头的实际问题，当处理大规模结构化线性模型时，而不会受到从头开始实现它们的障碍。该软件包的未来版本将包括对10个-对开折进行排序，以便更严格地实现高阶线性映射。此外，对更复杂的块结构的规范的改进支持旨在更好地利用冗余来自矩阵表示内的重复结构。竞争利益作者声明，他们没有已知的竞争性财务利益或个人关系，可能会影响本文报告的工作致谢我们要感谢卡尔蔡司基金会在“PRIME”项目下，DFG在“CoS-MoS”和“HoPaDyn”项目下，以及图林根自由州和欧洲社会基金在参考“2019 FGR 0100”下支持HyLoC研究小组在开发fastmat期间所获得的支持。我们感谢技术大学的开放获取出版基金对出版费用的支持。附录A. 防止Python性能损失：Cython部分由于其解释，抽象和许可（鸭子类型）的性质，Python并不特别以快速代码执行而闻名。为了缓解这一点，我们在整个架构中广泛使用Cython，通过尽可能减少Python解释器交互来减少额外的调用开销（在我们的面向对象模型中引入）。特别是对于组合了数千个小（N）运算符的无矩阵运算符 在fastmat的引擎盖下）变得势在必行，因为（多余的）解释器交互很快开始主导运行时。为了最小化调用开销，完整的类模型架构和所有内置类实现都利用Cython来编译代码并将其静态链接回Python API。通过这种方式，Python解释器不仅可以在包内执行流程（例如， 方法调用），但也适用于与Numpy的大多数交互（通过其提供的C-API），从而比纯（解释型）Python代码显着提高性能。为了避免运行时动态类型带来的运行时损失，fastmat在内部大量使用静态类型，并支持整数（8，16，32和64位），浮点和复杂（单精度和双精度）的数据类型另一个运行时损失是在内部数组切片操作期间创建大量的ndarray视图通过使用专用的可变跨步操作符来缓解这一问题，该操作符适用于数组，这极大地减轻了创建和垃圾收集许多短期Python对象（如数组视图）的压力附录B.类校准和执行路径优化由于现代CPU对数字运算进行了高度优化，因此对于非常小的变换大小，密集表示可能比无矩阵表示计算得更快-即使复杂性分析预测相反。这主要是由于复杂性模型的缩放不敏感性，但也受到处理器缓存和内存速度的影响。在这种情况下，使用传统的稠密然而，确定阈值的问题大小，从下面的密集表示应该是优选的，是高度个性化的任何特定的问题和处理系统，必须在运行时确定。在fastmat中，这个过程被称为校准，并且作为正常用户界面的一部分可用于任何Matrix类（也可用于用户定义的类）。为此，fastmat提供了一个简单的接口，用于一次性生成与问题大小无关的运行时估计模型（也考虑多个向量的同时处理）。在矩阵实例的实例化期间，估计其运行时性能和可比密集产品的运行时性能，给定校准数据在当前会话的上下文中可用 当最终使用φ或β时，可以立即选择特定数量的同时向量的最佳路径。通过这种方式，fastmat集成了运行时计算路径优化功能。附录C. 从用户的角度重载类为了提高可用性，fastmat的一个主要挑战是同时实现以下目标：首先，矩阵实例必须在数学上有意义的情况下表现相同，而不管上下文如何。因此，在拥抱鸭子Python的输入咒语，输入和输出净化是所有用户界面方法所必需的--不管它们是否受到重载的其次，必须能够轻松地定义新的或扩展现有的类，无论它们是内置的（Cython）还是用户定义的（Python），或者覆盖用户界面上任何类的特定部分最后，必须保持可读性、易用性和可重用性，以建立尽可能低的复杂性的用户体验。当重载类时，用户必须能够享受不必关心破坏内部API或功能的舒适位置直接在Matrix基类的类API入口方法上添加一个额外的输入准备层就可以实现所有目标。每个类API方法都负责输入合规性，并应用更高级的功能，例如预计算、结果缓存或运行时执行路径优化（校准，请参见附录B）。实际的实现代码在克里斯托弗·W· 瓦格纳，塞巴斯蒂安·森佩尔，扬·基希霍夫软件X 18（2022）1010138单独的私有方法。由于用户在实现自定义结构化矩阵时只重写这些私有方法，因此始终保证接口一致性。对于应用预计算缓存的属性，整个代码执行（和实现重载）机制如下：假设希望访问属性A.foo。存在被隐藏的属性A。_foo，它缓存计算结果，以便在所有后续查询中立即返回。在第一个查询期间，A.getFoo（）被调用作为计算'foo'的直接API入口点。此入口点处理接口完整性（类似于任何其他类API方法），并且不能直接重载相反，它将执行流重定向到A。getFoo（）用于实际的计算，这是一个用户会重载的精益方法。因此，我们认为，如果用户想要改变A.foo或A.getFoo（）的行为，重载A._getFoo（）和一个新的实现是所有需要做的。引用[1] 放大图片作者：Kannabner P，Angermann L.椭圆和抛物型偏微分方程的数值方法。 New York，NY，New York：Springer; 2003.[2] Deans SR. Radon变换及其应用。1993年原版的再版。Mineola，NY：DoverPublications.xii; 2007，p.295.[3] 路 德 维 希 ·D 欧 氏 空 间 上 的 Radon 变 换 Comm Pure Appl Math 1966;19（1）：49http://dx.doi.org/10.1002/cpa.3160190105网站。[4] Quinto ET. X射线层析成像和Radon变换导论. Providence，RI：AmericanMathematical Society（AMS）; 2006.[5] David TA，Hu Y.佛罗里达大学稀疏矩阵集合。 ACM Trans Math Software2011;38（1）. http://dx.doi.org/10.1145/2049662的网站。2049663[6] Shepp LA，Logan BF.头部的傅立叶重建。IEEE跨核科学1974;21：21-43.[7] Johnson SG，Frigo M.在实践中实施FFT。在：Burrus CS，编辑.快速傅立叶变 换 。 RiceUniversity， HoustonTX： Connexions;2008 ，URLhttp://cnx.org/content/m16336/.[8] FrigoM ， JohnsonS. FFTW3.ProcIEEE2005;93 （ 2 ） ： 216-31.http://dx.doi.org/10.1109/JPROC.2004.840301网站。[9]弗里戈·M一种快速傅里叶变换算法1999年ACM SIGPLAN编程语言设计与实现 会 议 论 文 集 。 New York ， NY ， USA ： Association for ComputingMachinery; 1999，p. 169-80. http://dx.doi.org/10.1145/301618.301661网站。[10] Frigo M，Johnson S. FFTW：FFT的自适应软件架构。收录于：1998年IEEE声学、语音和信号处理国际会议论文集（目录号98CH36181）。第3卷，1998年，第1381-4页，http://dx.doi.org/10.1109/ICASSP.1998.681704网站。[11][10]杨文，杨文.超声无损测量的频率子采样：采集、重建和性能。IEEETransUltrasonFerro-ElectrFreqControl2021;68 （ 10 ） ： 3174-91.http://dx.doi.org/10.1109/TUFFC的网站。2021.3085007。[12]Beck A ， Teboulle M. 线 性 反 问 题 的 一 种 快 速 迭 代 收 缩 保 持 算 法 SIAM JImaging Sci 2009;2（1）：183-202. 网址：//dx.doi.org/10.1137/080716542网站。[13]Tropp JA，Gilbert AC.通过 正交 匹配 追踪 从随机 测量 中恢 复信 号。IEEETransInformTheory2007;53（12）：4655http://dx.doi.org/10.1109/TIT.2007.909108网站。[14]布鲁克斯FP。神秘的人月周年纪念，转载与corr。，（新增4章）Addison-Wesley; 1995.[15]Semper S， Kirchhof J， Wagner C ， Krieg F ， Römer F ， Osman A ， DelGaldo G.使用无矩阵稀疏恢复算法的三维超声测量缺陷检测。第26届欧洲信号处理会议论文集。意大利罗马;2018年，http://dx.doi.org/10.23919/EUSIPCO.2018.8553074。[16]Semper S，Kirchhof J，Wagner C，Krieg F，Römer F，Del Galdo G.从压缩的三维超声频率测量中进行缺陷检测。2019年第27届欧洲信号处理会议第1-5页。http://dx.doi.org/10.23919/EUSIPCO.2019.8903133.[17]Wagner CW，Semper S，Römer F，Schönfeld A，Del Galdo G.基于压缩感知的超宽带信道冲激响应测量硬件架构。2020年第28届欧洲信号处理会议。2021 ， 第 1663-7 页 。 http://dx.doi.org/10.23919/Eusipco47968.2020 的 网 站 。9287454。[18]放大图片作者：Yadav M，Sheldon D.高斯过程的快速核插值。In：BanerjeeA，Jakumizu K，editors.第24届人工智能与统计国际会议论文集。机器学习研究论文集，卷。130，PMLR; 2021，p.2971//proceedings.mlr.press/v130/yadav21a.html网站。[19]Weise K，Poßner L，Müller E，Gast R，Knösche TR. Pygpc：Python的灵敏 度 和 不 确 定 性 分 析 工 具 箱 。 SoftwareX2020;11 ： 100450.http://dx.doi.org/10.1016/j.softx.2020.100450网站。