Source-linked AI summary
Schreyer Resolutions over the Exterior Algebra
Janko Boehm, Lakshmi Ramesh
TL;DR
Computing free resolutions over the exterior algebra supports coherent-sheaf cohomology through the BGG correspondence, while Schreyer methods also offer potential for parallel computation. This paper adapts a refined Schreyer algorithm using relative Gröbner bases, illustrates cohomology computations, and reports that commutative parallel techniques extend to the non-commutative setting.
Problem
Computing coherent-sheaf cohomology on projective space through free resolutions requires resolution methods for modules over the exterior algebra, and Schreyer-type algorithms also have potential for parallelization.
Source: §1 · pp. 1–2Method
The paper adapts the refined Schreyer algorithm to the anti-commutative setting, computing syzygies over lifted N-modules with relative Gröbner bases before projecting to the exterior algebra.
Source: §1 · p. 3, §3 · p. 7, §4 · p. 10Results
The paper gives examples of cohomology computations and shows that existing parallel techniques for the commutative case extend to the non-commutative setup.
Source: §1 · p. 2Takeaways & Limitations
The algorithm provides a route to coherent-sheaf cohomology computations via exterior-algebra resolutions and a basis for extending parallel Schreyer techniques to this setting.
Source: §1 · p. 2Free resolutions over the exterior algebra may be infinite, so the homological degree to compute must be bounded.
Source: §4.3 · p. 17, §6.2 · p. 22
Abstract
from arXiv · showhide
Schreyer's algorithm is usually the fastest way to determine a (typically non-minimal) free resolution of a finitely presented module over a polynomial ring. We adapt a refined version of Schreyer's algorithm to compute free resolutions over the exterior algebra, relying on relative Groebner bases. We illustrate the use of our algorithm for the computation of cohomology of coherent sheaves over projective space, which by the BGG correspondence can be computed via free resolutions over the exterior algebra. Schreyer's method relies on a tree traversal and thus has the potential for parallel computations. We report on ongoing work on a massively parallel implementation, observing that Gnawali's parallel approach over polynomial rings can be carried over to our setting.
1. Introduction
The paper adapts a refined Schreyer algorithm to compute free resolutions over the exterior algebra, using relative Gröbner bases. It motivates this work through sheaf cohomology via the BGG correspondence and the potential to parallelize Schreyer computations.
1. Introduction
- Schreyer-type algorithms use tree traversal and have potential for parallelization; the paper reports that commutative-case techniques extend to the non-commutative setting.The current implementation is a demonstrator, while a Singular-kernel implementation and a massively parallel version are under development.Source: §1 · pp. 1–2
- The refined Schreyer algorithm of [EMSS16] avoids computing lower-order terms that do not contribute to syzygies, improving on the original algorithm for polynomial rings.The paper adapts that approach to modules over the exterior algebra.Source: §1 · p. 2
- The BGG correspondence allows coherent-sheaf cohomology on projective space to be computed through free resolutions over the exterior algebra.The paper illustrates this application with cohomology computations based on its resolution algorithm.Source: §1 · p. 2
- The method adapts the refined Schreyer algorithm to the anti-commutative setting of N and uses relative Gröbner bases to compute exterior-algebra syzygies.It computes syzygies over a lifted N-module, then projects them to obtain syzygies over the exterior algebra.Source: §1 · pp. 2–3
2. Non-Commutative Fundamentals
The section establishes Gröbner-basis and syzygy tools for modules over the anti-commutative PBW algebra N. Its anti-commutative Schreyer theorem constructs a Gröbner basis for the syzygy module from pairwise S-vectors.
2.1. Gr¨obner Bases over N.
- Monomial orderings on N respect multiplication when the resulting leading monomials are nonzero, and module orderings must be compatible with the ring ordering.Polynomial-ring monomial orderings also work on N because the multiplication order affects only the coefficient.Source: §2.1 · pp. 3–4
- For terms with compatible module components, left division uses a quotient that accounts for the sign of reordering anti-commuting monomials.The quotient is defined for terms ax^αe_i and bx^γe_j when α ≤ γ.Source: §2.1 · pp. 3–4
- A module Gröbner basis is characterized by generating the lead module, and reduced division yields a normal form used to test membership through vanishing remainder.The standard presentation of an element need not be unique.Source: §2.1 · pp. 4–6
2.2. Syzygy Modules over N.
- A left syzygy is a tuple of coefficients whose linear combination of the generators is zero; all such tuples form the syzygy module.The associated map from the free module sends its canonical basis vectors to the generators, and the syzygy module is its kernel.Source: §2.2 · p. 6
- Pairwise S-vectors cancel leading terms, and their standard presentations produce syzygy vectors that form a Gröbner basis under the induced Schreyer ordering.The theorem applies to pairs whose leading monomials have a nonzero least common multiple; this is a non-commutative Schreyer theorem for solvable polynomial algebras [Lev05, Thm. 4.8].Source: §2.2 · pp. 6–7
3. Computing Syzygies over the Exterior Algebra
To compute syzygies over the exterior algebra E, the method lifts an E-module to N, computes syzygies there, and projects the results back. Relative Gröbner bases account for the quotient ideal during this process.
3. Computing Syzygies over the Exterior Algebra
- The computation lifts an E-module to an N-module, computes its syzygies over N, and projects them to obtain E-syzygies, repeating the lift-and-project process for successive syzygies.The lifted module's Gröbner basis is used as input to the adapted Schreyer algorithm.Source: §3 · pp. 7–8
3.1. Relative Gr¨obner Basis.
- Relative division reduces vectors using both the lifted module's Gröbner basis and the quotient ideal, leaving a remainder divisible by neither set of leading monomials.The quotient ideal is generated by the squares x_i^2.Source: §3.1 · pp. 8–9
- A Gröbner basis of an E-module is defined by canonical lifts that form a relative Gröbner basis of its preimage N-module.The module ordering on E is induced from the ordering on N through projection.Source: §3.1 · p. 8
- A Gröbner basis relative to I lifts to a Gröbner basis after adjoining generators of I, enabling Gröbner-basis computations for modules over the quotient ring.For the exterior algebra, the generators of I are the squares x_i^2.Source: §3.1 · p. 9
3.2. From N-syzygy to E-syzygy.
- To obtain E-syzygies, the lifted Gröbner basis includes generators of the ideal submodule I^m, and the nonzero projected Schreyer syzygies form a Gröbner basis of the E-syzygy module.The projection retains the first r coordinates corresponding to the original lifted generators.Source: §3.2 · p. 10
4. Refined Schreyer Algorithm
The refined Schreyer algorithm is adapted from polynomial rings to anti-commutative N-modules, where it computes syzygy-module Gröbner bases by building a Schreyer frame and lifting its lead terms. Relative Gröbner bases connect this computation to resolutions over the exterior algebra.
4. Refined Schreyer Algorithm
- The algorithm adapts the refined Schreyer method to N-modules, writing monomials in standard form to handle anti-commutative products and their signs.The refined method avoids terms not divisible by any basis element, since they contribute no coefficient to the lifted syzygy.Source: §4 · p. 10, §4.2 · p. 12
4.1. The Schreyer Frame.
- A Schreyer frame records lead-term maps through the resolution; the algorithm computes the lead syzygy module, then lifts each generator term by term to obtain syzygies.The resulting frame can be extended to a Schreyer resolution.Source: §4.1 · pp. 11–12
4.2. Lifting the Lead Syzygy Module.
- LiftTree and LiftSubtree recursively lift lead syzygy terms, retaining lower-order tails; the algorithms terminate and produce a Gröbner basis of Syz(G).The lifting cancels lead terms at each tree vertex, accounting for the anti-commutative sign.Source: §4.2 · pp. 12–13
15. For the third branch we obtain
The example traces a term-by-term LiftTree computation and gives the resulting syzygy. SchreyerOrderCheck compares terms recursively through the frame, and exterior-algebra resolutions may require a specified degree bound.
15. For the third branch we obtain
- The example’s lifted terms yield the syzygy vector −e′7 + ye′2 + ze′3 − e′15 − e′24, whose image includes the Gröbner-basis element 1 + ye′2 + ze′3.The complete term-by-term lifting is shown in Figure 2.Source: §15 · pp. 16–17, Figure 2 · p. 16
4.3. Avoiding Evaluations of the Schreyer Ordering.
- SchreyerOrderCheck compares terms by mapping their leading terms through the frame morphisms recursively until the base module ordering can decide their order.The procedure returns a Boolean comparison using the module ordering at the first level.Source: §15 · p. 17, §4.3 · p. 17
- Because free resolutions over the exterior algebra may be infinite, computations must specify the homological degree to reach.Hilbert’s syzygy theorem does not necessarily hold in this setting.Source: §4.3 · p. 17
5. Sheaf Cohomology via BGG Correspondence
The section uses the BGG correspondence to connect sheaf cohomology on projective space with free resolutions over the exterior algebra. It describes how Tate resolutions encode cohomology and illustrates computation of a minimal resolution.
5. Sheaf Cohomology via BGG Correspondence
- The BGG correspondence relates coherent sheaves on projective space to modules over the exterior algebra, making free resolutions a route to sheaf cohomology numbers.The paper describes this computation as preferred to using Čech complexes due to computation time.Source: §5 · pp. 17–19
- The Tate resolution’s terms encode the cohomology modules, and its Betti diagram arranges the sheaf’s cohomology dimensions across twists and cohomological degrees.The paper uses the Tate-resolution result to obtain information about sheaf cohomology.Source: §5 · p. 19
- To obtain a minimal free resolution, the method computes a Schreyer resolution and then uses Singular’s minres command to eliminate constant differential entries by linear algebra.Minimality is defined by homogeneous differential entries lying in the augmentation ideal.Source: §5 · p. 20
Example 5.1
- In the reported example, the Betti table from sresExt coincides with mresExt over the computed range except in the last column.The example computes a Schreyer resolution and then minimizes it after the full resolution is computed.Source: §5 · p. 20
6. Notes on Parallelisation
The section recasts refined Schreyer computations as parallel tasks coordinated by Petri nets, extending a polynomial-ring approach to the exterior-algebra setting. It describes an iterative lifting algorithm and a net for syzygy computation, while noting that implementation details and performance results remain future work.
6.1. Overview.
- Gnawali’s parallel approach for polynomial rings extends to exterior-algebra resolutions, with large examples such as those arising in the BGG correspondence as a target.The extension is ongoing joint work.Source: §6.1 · p. 21
- Independent term liftings expose parallelism; a dependency graph is traversed breadth-first to organize the computations.The Singular/GPI-Space framework uses Petri nets for coordination, with Singular as the computation and serialization layer.Source: §6.1 · p. 21, §6.2 · p. 21
6.2. The Singular/GPI-Space Framework.
- Petri nets coordinate computation through enabled transitions that consume and produce tokens, allowing task and data parallelism.The depicted example has T1 and T2 firing in parallel, while T2 can also fire data-parallel; the parallel-addition subnet combines lifting summands.Source: §6.2 · pp. 21–22, Figure 3 · p. 22, Figure 4 · p. 22
6.3. Iterative Schreyer Algorithm.
- The recursive LiftSubtree is reformulated iteratively: collect non-lower-order terms, find corresponding multiples of leading terms, and accumulate the resulting syzygy terms for addition.The terms can be added after the lift procedures finish, enabling those procedures to run in parallel.Source: §6.3 · pp. 22–23
6.4. Formulation as a Petri net.
- The Petri net assigns lead-syzygy generation and lifting to transitions, then combines their summands; the same net applies over N because addition is commutative.The exterior-algebra resolution is obtained by computing an N-Gröbner basis of the lifted syzygy module, applying ρ, and deleting zero images; a homological-degree bound is needed because resolutions may not terminate.Source: §6.2 · p. 22, §6.4 · p. 23, Figure 5 · p. 24
- Kernel-level transition implementations are planned to support the parallel computation and a fast sequential version, but implementation details and performance results are deferred.Source: §6.4 · p. 24