Computational Algebra with Attention: Transformer Oracles for Border Basis Algorithms
Di cosa parla
Si introduce un modo per accelerare la risoluzione di sistemi di equazioni polinomiali combinando un algoritmo simbolico tradizionale con un modello di deep learning chiamato Transformer: il modello funge da “oracolo” che riconosce e salta passaggi di calcolo particolarmente costosi. L'approccio mira a conservare la correttezza dei risultati mentre riduce i tempi di calcolo, e comprende anche una procedura di campionamento e una rappresentazione più compatta dei polinomi per l'addestramento.
Cosa permette di osservare
Consente di esplorare se e come l'apprendimento automatico può velocizzare calcoli simbolici senza perdere le garanzie formali, e quali scelte su campionamento e rappresentazione dei dati sono necessarie per ottenere questi benefici.
Dalla fonte
Solving systems of polynomial equations, particularly those with finitely many solutions, is a crucial challenge across many scientific fields. Traditional methods like Gr\"obner and Border bases are fundamental but suffer from high computational costs, which have motivated recent Deep Learning approaches to improve efficiency, albeit at the expense of output correctness. In this work, we introduce the Oracle Border Basis Algorithm, the first Deep Learning approach that accelerates Border basis computation while maintaining output guarantees. To this end, we design and train a Transformer-based oracle that identifies and eliminates computationally expensive reduction steps, which we find to dominate the algorithm's runtime. By selectively invoking this oracle during critical phases of computation, we achieve substantial speedup factors of up to 3.5x compared to the base algorithm, witho…