World Scientific
  • Search
  •   
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×

System Upgrade on Tue, May 28th, 2024 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

AN AXIOMATIC SETUP FOR ALGORITHMIC HOMOLOGICAL ALGEBRA AND AN ALTERNATIVE APPROACH TO LOCALIZATION

    https://doi.org/10.1142/S0219498811004562Cited by:16 (Source: Crossref)

    In this paper we develop an axiomatic setup for algorithmic homological algebra of Abelian categories. This is done by exhibiting all existential quantifiers entering the definition of an Abelian category, which for the sake of computability need to be turned into constructive ones. We do this explicitly for the often-studied example Abelian category of finitely presented modules over a so-called computable ring R, i.e. a ring with an explicit algorithm to solve one-sided (in)homogeneous linear systems over R. For a finitely generated maximal ideal 𝔪 in a commutative ring R, we show how solving (in)homogeneous linear systems over R𝔪 can be reduced to solving associated systems over R. Hence, the computability of R implies that of R𝔪. As a corollary, we obtain the computability of the category of finitely presented R𝔪-modules as an Abelian category, without the need of a Mora-like algorithm. The reduction also yields, as a byproduct, a complexity estimation for the ideal membership problem over local polynomial rings. Finally, in the case of localized polynomial rings, we demonstrate the computational advantage of our homologically motivated alternative approach in comparison to an existing implementation of Mora's algorithm.

    AMSC: 18E10, 18E25, 18G05, 18G10, 18G15, 13H99, 13P10, 13P20

    References

    • M.   Auslander and M.   Bridger , Stable Module Theory , Memoirs of the American Mathematical Society ( American Mathematical Society , Providence, RI , 1969 ) . Google Scholar
    • M. Barakat, Spectral filtrations via generalized morphisms, preprint, 2009 , arXiv:0904.0240 . Google Scholar
    • M. Barakat, The homalg Package — A GAP4 meta-package for homological algebra, 2007–2010, http://homalg.math.rwth-aachen.de/index.php/core-packages/homalg-package . Google Scholar
    • M. Barakat and M. Lange-Hegermann, LocalizeRingF orHomalg — Localize commutative computable rings at maximal ideals, 2009–2010, http://homalg.math.rwth-aachen.de/index.php/extensions/localizeringforhomalg . Google Scholar
    • M. Barakat and D. Robertz, J. Algebra Appl. 7(3), 299 (2008), arXiv:math.AC/0701146 DOI: 10.1142/S0219498808002813. Link, Web of ScienceGoogle Scholar
    • Y. A. Blinkovet al., The MAPLE package "Janet": II. Linear partial differential equations, Proc. 6th Int. Workshop on Computer Algebra in Scientific Computing (2003) pp. 41–54. Google Scholar
    • T. Breuer and S. Linton, The gap 4 type system: Organising algebraic algorithms, ISSAC '98: Proc. 1998 Int. Symp. Symbolic and Algebraic Computation (ACM, New York, 1998) pp. 38–45. Google Scholar
    • B. Buchberger, J. Symb. Comput. 41(4), 475 (2006), DOI: 10.1016/j.jsc.2005.09.007. Crossref, Web of ScienceGoogle Scholar
    • F. Chyzak, A. Quadrat and D. Robertz, Appl. Algebr. Eng. Comm. 16(5), 319 (2005), http://www-sop.inria.fr/members/Alban.Quadrat/PubsTem-poraire/AAECC.pdf DOI: 10.1007/s00200-005-0188-6. Crossref, Web of ScienceGoogle Scholar
    • F. Chyzak, A. Quadrat and D. Robertz, Applications of Time Delay Systems, Lecture Notes in Control and Information Sciences 352 (Springer, Berlin, 2007) pp. 233–264, http://wwwb.math.rwth-aachen.de/OreModules. CrossrefGoogle Scholar
    • P. M.   Cohn , Free Rings and Their Relations , 2nd edn. , London Mathematical Society Monographs   19 ( Academic Press Inc , London , 1985 ) . Google Scholar
    • T. Coquand and A. Spiwack, Towards constructive homological algebra in type theory, Calculemus '07/MKM '07: Proc. 14th Symp. Towards Mechanized Mathematical Assistants (Springer, Berlin, 2007) pp. 40–54. Google Scholar
    • D. A.   Cox , J.   Little and D.   O'Shea , Using Algebraic Geometry , 2nd edn. , Graduate Texts in Mathematics   185 ( Springer , New York , 2005 ) . Google Scholar
    • W.   Decker and C.   Lossen , Computing in Algebraic Geometry , Algorithms and Computation in Mathematics   16 ( Springer , Berlin , 2006 ) . Google Scholar
    • D.   Eisenbud , Commutative Algebra , Graduate Texts in Mathematics   150 ( Springer , New York , 1995 ) . CrossrefGoogle Scholar
    • A. Fabianska and A. Quadrat, Gröbner Bases in Control Theory and Signal Processing, Radon Series on Computational and Applied Mathematics 3, eds. H. Park and G. Regensburger (de Gruyter, Berlin, 2007) pp. 23–106. CrossrefGoogle Scholar
    • J. Gago-Vargas, J. Pure Appl. Algebra 185 (2002), DOI: 10.1016/S0022-4049(01)00136-0. Google Scholar
    • G.-M.   Greuel and G.   Pfister , A Singular Introduction to Commutative Algebra ( Springer , Berlin , 2008 ) . Google Scholar
    • G.-M.   Greuel , G.   Pfister and H.   Schönemann , Singular 3-1-0, A Computer Algebra System for Polynomial Computations , Centre for Computer Algebra ( University of Kaiserslautern , 2009 ) ,   http://www.singular.uni-kl.de . Google Scholar
    • R.   Hartshorne , Algebraic Geometry , Graduate Texts in Mathematics   52 ( Springer , New York , 1977 ) . CrossrefGoogle Scholar
    • P. J.   Hilton and U.   Stammbach , A Course in Homological Algebra , 2nd edn. , Graduate Texts in Mathematics   4 ( Springer , New York , 1997 ) . CrossrefGoogle Scholar
    • M.   Kreuzer and L.   Robbiano , Computational Commutative Algebra   1 ( Springer , Berlin , 2000 ) . CrossrefGoogle Scholar
    • T. Y.   Lam , Lectures on Modules and Rings , Graduate Texts in Mathematics   189 ( Springer , New York , 1999 ) . CrossrefGoogle Scholar
    • R. C. Laubenbacher and C. J. Woodburn, Beiträge Algebra Geom. 41(1), 23 (2000). Google Scholar
    • V. Levandovskyy, Non-commutative computer algebra for polynomial algebras: Gröbner bases, applications and implementation, Ph.D. thesis, University of Kaiserslautern, June 2005 . Google Scholar
    • A. Logar and B. Sturmfels, J. Algebra 145(1), 231 (1992), DOI: 10.1016/0021-8693(92)90189-S. Crossref, Web of ScienceGoogle Scholar
    • S.   Mac Lane , Homology , Classics in Mathematics ( Springer , Berlin , 1995 ) . Google Scholar
    • E. Mayr, Membership in polynomial ideals over ℚ is exponential space complete, STACS 89349, Lecture Notes in Computer Science (Springer, Berlin, 1989) pp. 400–406. Google Scholar
    • F. Mora, Computer Algebra, Lecture Notes in Computer Science 144 (Springer, Berlin, 1982) pp. 158–165. CrossrefGoogle Scholar
    • A. Quadrat and D. Robertz, J. Symb. Comput. 42(12), 1113 (2007), DOI: 10.1016/j.jsc.2007.06.005. Crossref, Web of ScienceGoogle Scholar
    • D. Robertz, Formal computational methods for control theory, Ph.D. thesis, RWTH Aachen, Germany, June 2006. This thesis is available at http://darwin.bth.rwth-aachen.de/opus/volltexte/2006/1586 . Google Scholar
    • J. J.   Rotman , An Introduction to Homological Algebra , 2nd edn. , Universitext ( Springer , New York , 2009 ) . CrossrefGoogle Scholar
    • J.-P. Serre, Ann. Math. (2) 61, 197 (1955), DOI: 10.2307/1969915. Crossref, Web of ScienceGoogle Scholar
    • J. T. Stafford, J. London Math. Soc. (2) 18(3), 429 (1978). Web of ScienceGoogle Scholar
    • The GAP group, GAP — groups, algorithms, and programming, version 4.4, 2006, http://www.gap-system.org . Google Scholar
    • The homalg project authors, The homalg project, 2003–2010, http://homalg.math.rwth-aachen.de/ . Google Scholar
    • C. A.   Weibel , An Introduction to Homological Algebra , Cambridge Studies in Advanced Mathematics   38 ( Cambridge University Press , Cambridge , 1994 ) . CrossrefGoogle Scholar
    • E. Zerz and V. Lomadze, SIAM J. Control Optim. 40(4), 1072 (2002), DOI: 10.1137/S0363012900374749. Crossref, Web of ScienceGoogle Scholar