基于Schubert多项式的稀疏插值

1基于Schubert多项式的稀疏多元多项式插值Priyanka Mukhopadhyay乔友明2018年10月14日，摘要我们通过A. Lasc oux和M. 20世纪80年代，科学技术在我国电影业的发展中占有重要地位。 这些多项式可使S多项式化，并形成多元多项式的线性基。在2003年，Lenart和Sottile引入了斜Schubert多项式，它推广了斜Schur多项式，并在Schubert基上扩展了广义Littlewood-Richardson系数。本文从计算复杂性理论的角度出发，对这两类多项式展开研究我们首先观察到斜舒伯特多项式，因此舒伯特多项式，在#P（当对非负整数输入求值时）和VNP中。我 们 的 主 要 结 果 是 一 个 确 定 性 的 算 法 ， 计 算 展 开 的 多 项 式 f 的 程 度 d 在 Z[x1，. . . ，xn]中的Schubert多项式的基础上，假设一个oracle计算Schubert多项式.这个算法运行在时间多项式中，在n，d和位的大小上进行了扩展. 这推广了Barvinok和Fomin在Schur基中的对称多项式的稀疏插值算法（Advances in Applied Mathematics，18（3）：271- 285），并且去随机化。实际上，我们的线性插值一般是一个满足某些自然性质的均匀线性基。上述结果的应用包括计算广义Littlewood-Richardson系数的新算法。1介绍多项式插值问题。经典的多项式插值问题开始于其中具有数据点s，（a1，b1），. . . ，（an+1，bn+1），其中ai，bi∈Q，aiajfori/=j，andndasks对于一元多项式f∈ Q[x] s. t. f（ai）= bi，其中i = 1，. . . ，n +1。虽然这样一个次数≤n的多项式存在且唯一，但取决于线性基的不同选择，牛顿、拉格朗日和范德蒙的几个公式已经成为经典。在理论计算机科学（TCS）中，以下问题也被称为多项式插值，其始于20世纪70年代：. .，xn]（F是一个域），通过写出它的单项式和表达式来计算f。几针对Quan t umTech n ono niveryofS ingapore（mukhopadyy）的查询，我是一个很好的朋友。com）。澳 大 利 亚 悉尼科技 大学量子计算与 智能系统中心 （Centre for Quantum Computation and IntelligentSystems，University of Technology，Sydney，Australia）com）。arXiv：1504.03856v4 [cs.CC] 2016年9月2已经提出了算法来解决这个问题[Zip79，BOT88，KY88，Zip90，KS01]。 一个自然的推广是考虑使用更强大的算术电路来表达f。在这个更一般的设置，这个问题被称为重建问题的算术电路[SY10，章。5]，f的单项式和表达式被看作是算术电路的一个子类，即深度为2的算术电路。各种模型的重建问题最近得到了相当大的发展[BC98，Shp 09，SV 08，KS 09，AMS 10，GKL 11，Kay12，GKL 12，GKQ 14]。如上所述，对于单变量多项式的插值，不同的公式取决于线性基的不同选择。另一方面，对于TCS设置中的多元多项式的插值（或更准确地说，重构），算法关键地依赖于计算模型。在后一种情况下，据我们所知，只考虑了单项式的线性基（被视为深度为2的单回路）。舒伯特多项式本文研究了多元多项式在TCS环境下的插值问题，但在多元多项式的另一种线性基，即Schubert多项式中。这为推广多元多项式插值问题提供了另一个自然的方向。此外，如下面将解释的，这样的插值算法可以用于计算非常感兴趣但尚未很好理解的几何形状中的某些量。在20世纪80年代，在您的计算机历史记录中，Lasco ux anddSchu？zenbergr[LS82]发现了SchubertPolyno m ials。对于D e f i n i t i n 1，S e e D e f i n i t i n 8或D e f i n i t i n 1 2，以及[Mac91，Man01]的详细结果。现在我们只指出（1）舒伯特多项式在Z[x1]中，. . ，xn]areindexedbyv=（v1，. . . ，vn）∈Nn，由Yv确定;2（2）Yv是f的随机数程度ni=1 五岛3舒伯特多项式有许多显著的性质。 它们构成了多元线性基础，变量多项式，并产生一个推广的牛顿插值公式的多元情况下[Las03，Sec.9.6]。此外，舒尔多项式是特殊的舒伯特多项式（13（1））。一个舒伯特多项式可以指数地包含许多单项式：完全齐次对称多项式是特殊的舒伯特多项式（13（2））。我们不清楚舒伯特多项式是否由于这些原因，在舒伯特基础上的插值不能覆盖的重建问题的上述结果，除非舒伯特多项式的算术电路复杂性更好地理解：目前，我们只能把舒伯特多项式在VNP。虽然舒伯特多项式由于其深刻的几何意义而主要被研究（参见例如[KM 05]），但它们确实具有在1982年引入后不久就被研究的某些算法方面。我发现，一个由La s c ou x和S c h u é t zen b e r g e r提出的简单的S chuberpolymials关注使用它们来计算Littlewood-Richardson系数[LS 85]。这一过程在程序系统[KKL92]中得到了很好的实现，其中包含一个使用舒伯特多项式的例程。另一方面，Schubert多项式算法方面的复杂性理论研究似乎缺乏，我们希望本文1定义12是舒伯特多项式的经典定义之一，而定义8在斜舒伯特多项式的上下文中定义舒伯特多项式。2.文献中，用置换代替Nn来表示Schubert多项式的情况比较常见。这两个索引集是等价的，通过排列和Nn之间的对应关系，如第2节所述我们在介绍中采用Nn，因为当处理固定数量的变量时，它们更容易处理3.本文中的算法在多项式的次数上运行于时间多项式中（2）这等于舒伯特多项式的指数以一元形式给出。3Σ这是朝着这个方向迈出的一小步。我们的成果。我们的主要结果是关于确定性插值的稀疏多项式的整数系数的舒伯特基础上，模的甲骨文计算舒伯特多项式。复杂度由表示的比特大小来衡量。定理1. 假设给定（1）对某个多项式f ∈ Z[x1，. . . ，X n]，f=v∈Γ avYv，av/= 0 ∈ Z且满足deg（f）≤ d且|Γ |≤ m;（2）一个预言，计算Schubert多项式在非负整数点上的求值。则存在此外，由于存在特定的地理位置，因此必须在Schubert polylynomial的数据库中添加扩展包。THE算法在n，d，m和log（v∈ Γ）的时间多项式中运行|的v|）的。事实上，定理1依赖于定理9中的算法，该算法适用于更一般的设置：通常，线性矩阵是这样的，其中，最小的最小值是唯一的。“我们的技术进行了更详细的讨论。定理1推广和去随机化Barvinok和Fomin的结果，他们在[BF 97]中提出了一个随机算法，在Schur基上插值稀疏对称多项式。如前所述，舒尔多项式是特殊的舒伯特多项式，并且舒尔多项式的雅可比-特鲁迪公式产生了计算它们的有效算法。因此，为了恢复Barvinok和Fomin的结果，我们提出了一种新的算法，即利用Schur多项式的有效算法来恢复Schubert多项式的计算。同样，对于那些具有有效求值过程4的舒伯特多项式，我们可以摆脱#P预言机以获得多项式时间插值算法。我们的第二个结果涉及舒伯特多项式的评价。 事实上，我们将使用舒伯特多项式的推广，即Lenart和Sottile [LS 03]定义的斜舒伯特多项式我们将在第2节中描述定义。现在，我们只注意到斜舒伯特多项式以类似于斜舒尔多项式如何推广舒尔多项式的方式推广舒伯特多项式。一个斜舒伯特多项式，记为Yw/v，其下标为v≤w∈ Nm，其中≤表示Bruhat阶5。 舒伯特多项式可以通过将w设置为对应于布鲁哈特阶中的最大置换定理2. 给定v，w ∈ N m为一元，a ∈ N n为二元，计算Yw/v（a）在#P中。推论3. 给定v ∈ Nn为一元数，a ∈ Nn为二元数，计算Yv（a）在#P中。注意，在定理2中我们有v， w∈ Nm，而在推论3中我们有v∈ Nn。这是因为，虽然对于舒伯特多项式，我们知道Yv（对于v∈ Nn）依赖于n个变量，但对于斜舒伯特多项式，这种关系并不清楚。最后，我们还研究了这些多项式的代数复杂性的框架定理4. 斜舒伯特多项式，因此舒伯特多项式，是在VNP。[4]例如，有行列式公式[Man01，Sec. 2.6]对于由2143索引的舒伯特多项式-避免排列（i< j< k< s. t.σ（j）<σ（i）<<σ（k））和321-避免置换（ki< σ（j）}|.给定一个置换σ ∈ S N，我们可以通过指定v i=|{j：j> i，σ（j）<σ（i）}|. 另一方面，给定一个码v∈ Nn，我们将一个置换σ ∈SN（N ≥ n）关联如下。（N将从施工程序中明确 首先，将σ（1）赋值为v1+ 1。σ（2）是第（v2+ 1）个数，如果需要，跳过σ（1）（即，如果σ（1）在前（v2+1）个数内σ（k）则是第（v k+1）个数，跳过σ（1），.. . . ，σ（k − 1）。例如，可以验证316245给出代码（2，0，3，0，0，0）=（2，0，3），反之亦然。给定一个码v，它的相关置换记为v。反之，置换σ ∈ SN的码记为c（σ）.很明显|σ|为|v|.基地设R是多项式环Z[x]的一个（可能非真）子环. 设M是R作为Z-模的一个基. M通常由某个索引集Λ索引，并且M={t λ|λ ∈ Λ}。对于R = Z [ x ] ，x_ample_A=Nn， 并 且 对 于 R={s_y_mm_e_tri_c_p_y_nomial_s}，d_A ={ p_t_i_n_Nn}。f∈ R可以唯一地表示为f =λ∈Γa λ t λ，a λ 0∈ Z，t λ∈ M，和一个有限的Γ ε Λ.Klivans和Spielman的结构。 我们提出了一个Klivans和Spielman的结构，这是这里去随机化的关键。给定正整数m、n和0 <<$1<，设t=<$m2n/<$m。 Lettdeanth e ntherpositiveinteger，并且f ixaprimeplargerthanth end。 Now_d_e在N_n中定义一组t个向量为KS（m，n，n，d，p）：={c（1），. . . ，c（t）}乘c（k）= k i−1mod p，其中i ∈ [n]。 记thatc（k）≤p=O（m2ndf）. 从KS开始，我们最需要的是下面的内容。引理6（[KS01，引理3]）。设e（1），. . .，e（m）是来自N n的m个不同的向量，{0，1，. . . ，d}。然后Pr[kc（k），e（j）nredistinctforj∈[m]]≥1−m2n/t≥1−n在#P和VNP上。#P的标准定义如下：函数f：n∈N{0， 1}n → Z在#P中，如果存在多项式时间图灵机M和多项式p，s. t。 对任意x ∈ {0，1} n，f（x）=|{y ∈ {0，1} p（n）s.t.（x，y）{|.在第3节定理2的证明中，我们发现考虑输出非负整数的图灵机类（而不是（fjustacceptoreject），且ff：n∈N{0，1}n→Ns. t. 这是一个不寻常的问题，图灵机M和多项式p，s.t. 对任意x ∈ {0，1}n，f（x）=y∈{0，1}p（n）M（x，y）.[7]这被称为置换的莱默码;例如参见[Man 01，第2.1节]。7−如[dCSW13]中所述，这样的函数也在#P中，因为我们可以构造一个通常的图灵M ′是一个随机群，它有3个随机数s（x，y，z），且M ′（x，y，z）满足zσ（k），或者σ（j）σ（i）。<这是因为π由于转置τik而增加了一个反演。所以在i和k之间的任何位置，σ都不能取σ（i）和σ（k）之间的值。否则，π中的反转数将改变超过1。取传递闭包给出Bruhat阶（≤）。Bruhat阶的最大元素是π0= N，N − 1，. . . ，1，其代码为d =（N-1，N-2，. . . ，1）。标号Bruhat阶是斜Schubert多项式定义的关键。虽然将其命名为订单，但它实际上是一个具有多个标记边的有向图，其中顶点在S N中的Permutations中，Forσstec<π标准差 σ −1π= τst，s ≤ j j，否则为1，因为s α中的每个指数向量都被yα支配（[BF97，Sec.二、2]）。 （Aistheupperrtriangularmatixh it i a l o n a t ia ）s α的相关前导单项式是xα。回顾过去，舒尔多项式形成I友好基的事实是Barvinok-Fomin算法[BF 97]的数学支持8.我们知道，对于非多边形多边 然而，我们所知道的唯一参考文献是[Sap16，pp. 10，脚注1]，其中没有提供细节因此，为了完整性，我们描述了克服这一点的过程[9]注意，虽然Λ已经依赖于n，但我们觉得明确指定n为K的参数更清楚，如命题17所示。·11′CΣ（飞机4.2插值友好基在本节中，我们在插值友好的基础上执行确定性稀疏多项式插值我们的想法是将Barvinok-Fomin算法的结构与Klivans-Spielman算法的一些我们首先简要回顾一下Klivans-Spielman算法的思想[KS 01，第6.3节]。假设我们要插值f∈ Z [x1，. . .，xn]，其中m是d次单项式。他们的算法利用地图φc（x1，. . . ，xn）=（yc1，. . . ，y cn）（2）其中c =（c1，. . . ，cn）∈（Z+）n. 如果c满足性质：ε e/= e ′∈ f，ε c，eε c，eε，则我们可以将多变量多项式的插值简化为单变量多项式的插值：首先应用单变量多项式插值（基于Vandermonde矩阵）以获得一组系数。然后，为了恢复指数，将φ c修改为φ ′（x1，. . . ，xn）=（p1y c1，. . . ，p n y cn），（3）当您需要一个不受约束的程序时，请不要考虑效率问题。通过对系数的两个集合进行比较，我们可以计算指数。注意，c的分量需要很小才能使单变量插值有效。 为了得到这样的c，Klivans和Spielman给出了n，m，d中的一个小多项式和一个测试向量cs.t.的错误概率<$∈（0，1）-集。在概率为1−1的情况下，来自这个集合的向量满足上述性质。此外，这些组件时间复杂度为O（m2nd/n）. 这种结构见第6节第2节。现在假设M是R Q[x]的（K，LA）-友好基，我们想恢复f=λ∈Γaλtλ度≤ d，且|Γ |= m。为了将上述思想应用于任意的I-友好基M，策略是提取前导单项式w.r.t. 洛杉矶然而，由于每个基多项式可能非常复杂，因此存在许多其他非前导单项式，它们可能会干扰前导单项式。具体而言，我们需要解释以下几点：(1) 在映射φc之后是否出现极大的系数，从而导致单变量插值过程效率低下？(2) 在映射φ c之后是否保持某些引导单项式？ (That是，在φ c下的每一个前导单项式的像是否会被非前导单项式抵消？）我们可以立即认识到，对我友好的基地就是为了克服上述问题而设计的(1)很容易：通过K-有界性质，对于f中的任何单项式xu，Coeff（u，f）的绝对值由K·（λ）有界|a λ|）. 因此，f在φc下的象的系数是有界的通过O. n+ d·K · Σ|一|-是的 (2)也不难克服;见下面定理9的证明。λ）这些属性在Barvinok-Fomin算法中隐式使用。最后一点需要注意的是：如果与单项式基的情况不同，这个过程不能一次产生所有的前导单项式，我们可能需要得到一个t λ和它的系数，减去它，然后重新计算。 这一要求充分利用了计算机的效率。 由于这是tλ（a）的一个预处理，与插值问题没有直接关系，我们假设一个预言机，它的索引为λ ∈ Λ，输入为a ∈ Nn，并返回t λ（a）.定理9. 设M={t λ|λ ∈ Λ}是R <$Z [x]的（K，L A）-友好基，K= K（λ，n），A是（0，1）可逆矩阵. 给定对计算a∈Nn的基多项式tλ（a）的oracle O = O（λ，a）的访问，存在确定性算法，给定包含f =λ12CDΣ我Σλ∈Γaλtλ，aλf=0∈Z，其中f（f）≤dandd|Γ|≤m，computesuchanexpansionf在时间上的poly（n，d，m，log（λ| a λ|），log K）。证据我们首先介绍了算法。 回想一下映射φc和φ ′在等式（2）中定义，等式（3）。输入：一个黑盒B，包含f ∈ R <$Z [x1，. . . ，xn]的条件下满足：（1）deg（f）≤ d;（2）f在M-基中有≤ m项一个预言机O=O（λ，a）计算tλ（a），其中a∈Nn.Σ输出：展开式f =λ∈Γa λ t λ。算法：1. 利用引理6，构造Klivans-Spielman集KS = KS（m，n，1/ 3，nd，p）.2. 对于KS中的每个向量c，做：(a) fc←0.i ←0. d ←A c.(b) 当我是，做：i. 将映射φd应用于B − fc（在O的帮助下），并使用单变量插值算法以获得g（y）=ki=0 比伊岛如果g（x）≥0，则break。ii. 将映射φ′应用于B − fc（借助O），并使用单变量插值算法以获得g′（y）=ki=0比伊岛iii. 从bk和b′，计算相应的单项式xe及其系数ae。杨永从x，计算相应的标签ν ∈Λ，并设置aν ← ae。iv. fc← fc+aν tν。i ← i+ 1。3. 取fc/c的大部分并输出。我们证明了上述算法的正确性。 如前所述，设eλ为tλw.r.t. 洛杉矶注意，由于A T是（0，1）-矩阵，因此向量A Te λ中的条目在{0，1，. . .，nd}。 利用KS（m，n，1/3，nd，p）的性质，从c ∈ KS开始，至少有2/3的向量满足条件c，ΔTeλ∈r，a t in t i n g，at in t i n g，ati n t i n g，a t i n t i n g，a t i n t i n g. “我们假设对于任何可区分向量，算法输出正确的展开，因此步骤（3）将成功。确定一个区别向量c。 当e λ/= e λ′，且λ/= λ ′且A可逆时，存在唯一的ν∈ Λ s.t. eν在λ ∈ Γ上的λ∈ c，ATe λ∈处达到最大值。当λ c，ATeλ =λ c， eλ =λ d， eλ时，根据M是LA相