Substitution and quotient of the isotropy group action

Technische Samenvatting: Substitutie en Quotiënt van de Isotropiegroep-actie

Probleemstelling
Het artikel behandelt de uitdaging van het ontdekken van nieuwe, niet-triviale geparametriseerde oplossingsverzamelingen voor de Brent-vergelijkingen, die de algoritmen voor matrixvermenigvuldiging beheersen. Specifiek richten de auteurs zich op het systeem $B(m, n, p|r)$, waarvan de oplossingsverzameling $V(m, n, p|r)$ de tensor-decomposities beschrijft van de matrixvermenigvuldigingstensor $\langle m, n, p \rangle$ met rang $r$.

Een primaire hindernis bij het verkennen van deze oplossingsverzamelingen is de aanwezigheid van een positie-dimensionale isotropiegroep-actie $I(m, n, p|r)$. Deze groep bestaat uit vier componenten: de de Groote (sandwiching) actie, layer scaling, permutatie van rang-één summanden, en $S_3$-symmetrie. Omdat de oplossingsverzameling invariant is onder deze groep, leiden standaardmethoden voor het vastzetten van gedeeltelijke oplossingen en het uitvoeren van substitutie vaak tot gereduceerde systemen waarbij de resulterende geparametriseerde oplossingen tot dezelfde isotropiegroep-baan behoren als de oorspronkelijke oplossing. Bijgevolg zijn deze "nieuwe" oplossingen slechts symmetrie-kopieën van bekende oplossingen, wat faalt in het leveren van werkelijk onderscheidende algoritmen. De auteurs beogen een methode te ontwikkelen om gedeeltelijke oplossingen vast te zetten zodanig dat de resulterende geparametriseerde verzameling intersecteert met onderscheidende isotropiegroep-banen, waardoor zij oneindig veel inequivalente algoritmen genereren.

Methodologie
De voorgestelde methodologie integreert instrumenten uit de Lie-groeptheorie met numerieke algebraïsche meetkunde. De kernaanpak bestaat uit het analyseren van de relatie tussen de nulruimte van de Jacobiaan-matrix en de raakruimte van de groep-banen.

1. Geometrisch Kader: De auteurs modelleren de oplossingsverzameling $V(m, n, p|r)$ als een variëteit gefolieerd door de banen van de isotropiegroep $I(m, n, p|r)$. Het vastzetten van een gedeeltelijke oplossing komt overeen met de intersectie van deze variëteit met een affiene coördinaat lineaire ruimte $L_I$.
2. Nulruimte- en Raakbasismatrices:
   • Nulruimte-basismatrix ($N(s)$): Afgeleid van de Jacobiaan-matrix $J(s)$ van de Brent-vergelijkingen bij een gladde oplossing $s$. De rang $d$ vertegenwoordigt de lokale dimensie van de oplossingsverzameling.
   • Raakbasismatrix ($T(s)$): Geconstrueerd met behulp van de infinitesimale generatoren van de Lie-groep-actie (specifiek de de Groote en de layer scaling groepen). De rang $d_T$ vertegenwoordigt de dimensie van de groep-baan die door $s$ gaat.
3. Selectiecriterium: De auteurs stellen een eerste-orde criterium voor om een deelverzameling van variabelen $I$ te selecteren om vast te zetten. Zij zoeken naar een indexverzameling $I$ waarvoor geldt:
   $$\text{rank } N(s) - \text{rank } N_I(s) > \text{rank } T(s) - \text{rank } T_I(s)$$
   waarbij $N_I(s)$ en $T_I(s)$ submatrices zijn die beperkt zijn tot rijen geïndexeerd door $I$.
   • Als de ongelijkheid strikt geldt, bezit het gereduceerde systeem lineaire richtingen bij $s$ die niet tangent zijn aan de groep-baan. Dit impliceert dat de gereduceerde oplossingsverzameling oneindig veel onderscheidende groep-banen snijdt.
   • Als de rangen gelijk zijn, blijft het gereduceerde systeem waarschijnlijk binnen een enkele baan (of een eindige vereniging van banen), wat geen nieuwe inequivalente oplossingen oplevert.
4. Implementatie: De methode is geïmplementeerd in Julia. Het proces omvat:
   • Het verifiëren van de gladheid van een bekende oplossing via deflatie-sequenties.
   • Het berekenen van $J(s)$, $N(s)$, en $T(s)$.
   • Het zoeken naar indexverzamelingen $I$ die aan de rang-gap conditie voldoen.
   • Het oplossen van het resulterende gereduceerde polynoom-systeem (vaak met behulp van Gröbner-bases via Oscar.jl) om geparametriseerde curven of hogere-dimensie verzamelingen te verkrijgen.

Kernbijdragen

• Theoretisch Criterium: Het artikel stelt een rigoureus eerste-orde criterium vast (Vergelijking 3.10) gebaseerd op het verschil tussen de codimensie van de vastgezette variabelen in de nulruimte versus de raakruimte. Dit criterium garandeert dat het substitutieproces oplossingen in verschillende isotropiegroep-banen oplevert.
• Expliciete Constructie: De auteurs bieden expliciete formules voor het berekenen van de raakbasismatrix $T(s)$ voor de Brent-vergelijkingen, waarbij rekening wordt gehouden met de specifieke structuur van de de Groote en de layer scaling acties.
• Algoritmisch Kader: Er wordt een praktische, stapsgewijze procedure geschetst voor het transformeren van bekende oplossingen naar families van inequivalente oplossingen, waarbij de valkuilen van "geïsoleerde oplossingen" of "dezelfde baan" worden omzeild.

Resultaten
De auteurs hebben hun methode toegepast op verschillende bekende oplossingen van de Brent-vergelijkingen:

1. $V(4, 4, 4|48)$ (Oplossing van Dumas, Pernet en Sedoglavic):

   • De oplossing heeft een lokale dimensie van 151, terwijl de baan-dimensie 141 is.
   • Door 2082 variabelen vast te zetten, hebben de auteurs het systeem gereduceerd tot 222 variabelen.
   • De resulterende oplossingsverzameling is een eendimensionale curve die oneindig veel punten bevat die behoren tot onderscheidende $I(4, 4, 4|48)$-banen. Dit levert oneindig veel inequivalente algoritmen op voor $4 \times 4$ matrixvermenigvuldiging met 48 vermenigvuldigingen met rationale coëfficiënten.
   • Grotere rang-gaps werden ook gevonden, wat hogere-dimensie geparametriseerde verzamelingen mogelijk maakte.

2. $V(4, 4, 4|49)$ (AlphaTensor-oplossing):

   • De oplossing heeft een lokale dimensie van 197 en een baan-dimensie van 143.
   • Het vastzetten van 2344 variabelen reduceerde het systeem tot 8 variabelen, wat een eendimensionale geparametriseerde curve van inequivalente oplossingen opleverde.
   • Het vastzetten van 2269 variabelen resulteerde in een gereduceerd systeem met 83 variabelen en een 9-dimensionale oplossingsverzameling, wat het vermogen aantoont om hoog-dimensionale families van nieuwe algoritmen te genereren.

3. $V(3, 3, 3|23)$ (Laderman-oplossing):

   • De oplossing heeft een lokale dimensie van 76 en een baan-dimensie van 70.
   • Het vastzetten van 613 variabelen reduceerde het systeem tot 8 variabelen, wat een eendimensionale curve van inequivalente oplossingen produceerde.
   • Het vastzetten van 574 variabelen leverde een zes-dimensionale geparametriseerde oplossingsverzameling op.

Betekenis
Het artikel beweert dat deze methode erin slaagt de beperkingen van eerdere substitutietechnieken te overwinnen, die vaak faalden om tussen symmetrie-equivalente oplossingen en werkelijk nieuwe algoritmen te onderscheiden. Door gebruik te maken van de raakbasismatrix om "transversale" richtingen ten opzichte van de groep-actie te identificeren, kunnen de auteurs systematisch niet-triviale geparametriseerde families uit bekende oplossingen extraheren.

De primaire betekenis ligt in het vermogen om oneindig veel inequivalente algoritmen voor matrixvermenigvuldiging te genereren vanuit een enkele bekende oplossing. Bijvoorbeeld, de parametrisatie van de rationale oplossing voor $4 \times 4$ matrixvermenigvuldiging met 48 vermenigvuldigingen demonstreert dat er niet slechts één zodanig algoritme is, maar een oneindige familie van hen met rationale coëfficiënten. Dit breidt het bekende landschap van matrixvermenigvuldigingsalgoritmen uit en biedt een systematisch hulpmiddel voor het verkennen van de geometrie van de Brent-vergelijkingen. De auteurs merken op dat hoewel de methode rust op de assumptie van transversale intersectie, numerieke experimenten de effectiviteit ervan bevestigen voor de geteste gladde oplossingen.