Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Computational algorithms for algebras
Stockholm University, Faculty of Science, Department of Mathematics.
2009 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

This thesis consists of six papers.

In Paper I, we give an algorithm for merging sorted lists of monomials and together with a projection technique, we obtain a new complexity bound for the Buchberger-Möller algorithm and the FGLM algorithm.

In Paper II, we discuss four different constructions of vector space bases associated to vanishing ideals of points. We show how to compute normal forms with respect to these bases and give complexity bounds. As an application we drastically improve the computational algebra approach to the reverse engineering of gene regulatory networks.

In Paper III, we introduce the concept of multiplication matrices for ideals of projective dimension zero. We discuss various applications and, in particular, we give a new algorithm to compute the variety of an ideal of projective dimension zero.

In Paper IV, we consider a subset of projective space over a finite field and give a geometric description of the minimal degree of a non-vanishing form with respect to this subset. We also give bounds on the minimal degree in terms of the cardinality of the subset.

In Paper V, we study an associative version of an algorithm constructed to compute the Hilbert series for graded Lie algebras. In the commutative case we use Gotzmann's persistence theorem to show that the algorithm terminates in finite time.

In Paper VI, we connect the commutative version of the algorithm in Paper V with the Buchberger algorithm.

Place, publisher, year, edition, pages
Stockholm: Department of Mathematics, Stockholm University , 2009. , 9 p.
Keyword [en]
Hilbert function, Gröbner basis, zero-dimensional ideal, affine variety, projective variety, run-time complexity
National Category
Mathematics
Research subject
Mathematics
Identifiers
URN: urn:nbn:se:su:diva-31552ISBN: 978-91-7155-974-6 (print)OAI: oai:DiVA.org:su-31552DiVA: diva2:277600
Public defence
2009-12-18, Sal 14, hus 5, Kräftriket, Stockholm, 10:00 (English)
Opponent
Supervisors
Note
At the time of doctoral defence, the following papers were unpublished and had a status as follows: Paper 3: Manuscript. Paper 4: Manuscript. Paper 5: Manuscript. Paper 6: ManuscriptAvailable from: 2009-11-26 Created: 2009-11-19 Last updated: 2009-11-20Bibliographically approved
List of papers
1. Vector space bases associated to vanishing ideals of points
Open this publication in new window or tab >>Vector space bases associated to vanishing ideals of points
2010 (English)In: Journal of Pure and Applied Algebra, ISSN 0022-4049, E-ISSN 1873-1376, Vol. 214, no 4, 309-321 p.Article in journal (Refereed) Published
Abstract [en]

In this paper we discuss four different constructions of vector space bases associated to vanishing ideals of points. We show how to compute normal forms with respect to these bases and give new complexity bounds. As an application, we drastically improve the computational algebra approach to the reverse engineering of gene regulatory networks.

Place, publisher, year, edition, pages
Elsevier, 2010
National Category
Mathematics
Research subject
Mathematics
Identifiers
urn:nbn:se:su:diva-31521 (URN)10.1016/j.jpaa.2009.05.013 (DOI)000273248700002 ()
Available from: 2009-11-19 Created: 2009-11-19 Last updated: 2017-12-12Bibliographically approved
2. Complexity of comparing monomials and two improvements of the Buchberger-Möller algorithm
Open this publication in new window or tab >>Complexity of comparing monomials and two improvements of the Buchberger-Möller algorithm
2008 (English)In: Lecture Notes in Computer Science, ISSN 0302-9743, E-ISSN 1611-3349, Vol. 5393, 105-125 p.Article in journal (Refereed) Published
Abstract [en]

We give a new algorithm for merging sorted lists of monomials. Together with a projection technique we obtain a new complexity bound for the Buchberger-Möller algorithm.

Place, publisher, year, edition, pages
Springer, 2008
National Category
Mathematics
Research subject
Mathematics
Identifiers
urn:nbn:se:su:diva-31520 (URN)10.1007/978-3-540-89994-5 (DOI)
Available from: 2009-11-19 Created: 2009-11-19 Last updated: 2017-12-12Bibliographically approved
3. A Buchberger like algorithm without monomial orderings: the graded commutative case
Open this publication in new window or tab >>A Buchberger like algorithm without monomial orderings: the graded commutative case
(English)Manuscript (preprint) (Other academic)
Abstract [en]

We analyze an algorithm to compute vector space bases for graded commutative algebras. The algorithm does not require a monomial ordering, but we show that when we use a monomial ordering, there is a strong connection to the Buchberger algorithm.

National Category
Mathematics
Research subject
Mathematics
Identifiers
urn:nbn:se:su:diva-31519 (URN)
Available from: 2009-11-19 Created: 2009-11-19 Last updated: 2011-03-14Bibliographically approved
4. An algorithm to determine the Hilbert series for graded associative algebras
Open this publication in new window or tab >>An algorithm to determine the Hilbert series for graded associative algebras
(English)Manuscript (preprint) (Other academic)
Abstract [en]

In this paper we present an algorithm to compute the Hilbert series for quotients of the free algebra with homogeneous two-sided ideals. We also give a modified version of the algorithm for quotients of the polynomial ring. The algorithms are implemented in a computer program named ``aalg'' and we compare running times with other computer algebra programs.

National Category
Mathematics
Research subject
Mathematics
Identifiers
urn:nbn:se:su:diva-31518 (URN)
Available from: 2009-11-19 Created: 2009-11-19 Last updated: 2011-03-14Bibliographically approved
5. Non-vanishing forms in projective space over finite fields
Open this publication in new window or tab >>Non-vanishing forms in projective space over finite fields
2010 (English)In: Journal of Commutative Algebra, ISSN 1939-2346, Vol. 2, no 4, 435-443 p.Article in journal (Refereed) Published
Abstract [en]

We consider a subset of projective space over a finite field and give a geometric description of the minimal degree of a non-vanishing form with respect to this subset. We also give bounds on the minimal degree in terms of the cardinality of the subset.

National Category
Mathematics
Research subject
Mathematics
Identifiers
urn:nbn:se:su:diva-31517 (URN)10.1216/JCA-2010-2-4-437 (DOI)
Available from: 2009-11-19 Created: 2009-11-19 Last updated: 2011-04-08Bibliographically approved
6. Multiplication matrices and ideals of projective dimension zero
Open this publication in new window or tab >>Multiplication matrices and ideals of projective dimension zero
2012 (English)In: Mathematics in Computer Science, ISSN 1661-8270, Vol. 6, no 1, 43-59 p.Article in journal (Refereed) Published
Abstract [en]

We introduce the concept of multiplication matrices for ideals of projective dimension zero. We discuss various applications and, in particular, we give a new algorithm to compute the variety of an ideal of projective dimension zero.

Place, publisher, year, edition, pages
Birkhäuser Verlag, 2012
National Category
Mathematics Algebra and Logic
Research subject
Mathematics
Identifiers
urn:nbn:se:su:diva-31516 (URN)10.1007/s11786-012-0108-7 (DOI)
Available from: 2009-11-19 Created: 2009-11-19 Last updated: 2013-05-17Bibliographically approved

Open Access in DiVA

fulltext(160 kB)562 downloads
File information
File name FULLTEXT02.pdfFile size 160 kBChecksum SHA-512
b4447b4cec7c79884958fc2dc9797af007dbe166688071634233b6d089fc5232320947cd3c1d80789973264a26c47f38df5bb0462cc037cef2655a67440e4e9a
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Lundqvist, Samuel
By organisation
Department of Mathematics
Mathematics

Search outside of DiVA

GoogleGoogle Scholar
Total: 562 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 1035 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf