Álgebra Computacional | Computational Algebra
URI permanente desta comunidade:
Navegar
Percorrer Álgebra Computacional | Computational Algebra por assunto "Algebra"
A mostrar 1 - 2 de 2
Resultados por página
Opções de ordenação
- Computing congruences and endomorphisms for algebras of type (2m, 1n)Publication . Pereira, Rui Barradas; Araújo, João; Bentz, Wolfram; Sequeira, LuisAtualmente a principal aplicação de software para semigrupos é a package de GAP chamada Semigroups [29], em articulação com a package Smallsemi [13]. O GAP [17] é um sistema e linguagem de programação para álgebra discreta computacional. Embora estas packages ofereçam muitas opções de cálculo e forneçam uma biblioteca de todos os semigrupos até o tamanho 8, várias operações de semigrupos importantes não estão disponíveis. Em parte, isto deve-se ao facto de a arquitetura subjacente ser voltada para a teoria de grupos e os semigrupos frequentemente requerem técnicas algorítmicas que são mais próximas das empregadas na Álgebra Universal do que daquelas usadas em grupos. Existem maneiras de construir álgebras a partir das existentes (produtos diretos etc.), mas a operação inversa é crítica: decompor uma dada álgebra em outras menores. Este tipo de decomposição é especialmente importante em semigrupos, pois mesmo a estrutura de semigrupos muito pequenos pode ser muito obscura. Até agora não existe uma ferramenta computacional geral para decompor semigrupos. Por exemplo, o GAP já contém código para encontrar todas as congruências de classes muito particulares de semigrupos, mas está muito longe de fornecer um método geral. A situação é ainda pior em relação aos endomorfismos. O objetivo da package CREAM (Algebra CongRuences, Endomorphisms and AutomorphisMs) é resolver esta situação implementando algoritmos eficientes para calcular congruências, endomorfismos e automorfismos de álgebras do tipo (2m, 1 n). Vários algoritmos gerais (como em [15]) serão adaptados para o contexto da teoria de semigrupos e mais geralmente para álgebras do tipo (2m, 1 n ) cobrindo assim grupos e semigrupos mas também álgebras unárias e também loops, campos, anéis, semianéis, álgebras de Lie, MV-álgebras, Meadows, álgebras de lógica, etc. Estes algoritmos serão implementados em GAP. Isso incluirá as seguintes questões: • Dada uma álgebra finita A do tipo (2m, 1 n ), encontrar todas as congruências de A, pelo menos tão rápido quanto os programas existentes (ou seja, o código produzido será geral e pelo menos tão rápido quanto o código que existe para classes específicas de álgebras apenas); • Dada uma álgebra finita A do tipo (2m, 1 n ), encontrar todos os endomorfismos de A; em particular, o código deve calcular efetivamente os automorfismos de A, uma ferramenta que essencialmente existe apenas para grupos. Uma álgebra universal é uma estrutura algébrica que consiste num conjunto A e numa coleção de operações sobre A. Uma operação n-aria sobre A é uma função que tem como entrada um n-tuplo de elementos de A e retorna um elemento de A. Neste contexto só estão a ser consideradas operações com aridade 1 ou 2, i.e. operações unárias e binárias. Uma álgebra do tipo (2m, 1 n ) é uma álgebra universal com m operações binárias e n unárias. Este uso genérico da package CREAM depende de teoremas de álgebra universal. Isto tem custos, pois teoremas de tipos específicos de álgebras (e.g. grupos, semigrupos, etc) não podem ser usados para reduzir o espaço de procura e melhorar a performance. Canon e Holt [10], usaram vários algoritmos inteligentes e teoremas específicos de grupos para produzir código mais rápido que a package CREAM a calcular automorfismos de grupos com ordens maiores. Analogamente, Mitchell et al. [29] usaram teoremas da teoria de semigrupos para calcular eficazmente automorfismos e congruências de semigrupos completamente 0-simples. Mas estes estão entre os poucos casos de código GAP disponível que é mais rápido que a package CREAM que é de uso mais generalizado. Para a maioria de outras classes de álgebras de tipo (2m, 1 n ) a package CREAM é mais rápida a calcular auto[endo]morfismos/congruências. Um dos algoritmos principais implementado na package é o algoritmo de Freese descrito em [15] que calcula congruências principais para uma álgebra universal. Para chegar a esta performance a package CREAM usa uma mistura de algoritmos standard de álgebra universal juntamente com ferramentas de procura eficiente por modelos finitos de fórmulas de primeira ordem e a implementação de partes de código em C. Em geral, calcular congruências de álgebras é uma tarefa difícil. Existem vários teoremas descritivos para diferentes tipos de álgebra e algumas ferramentas computacionais para calcular congruências para álgebras finitas, mas geralmente essas ferramentas são aplicáveis a um conjunto muito específico e estreito de álgebras. O nosso objetivo era fornecer uma ferramenta eficaz para calculá-los para álgebras finitas do tipo (2m, 1 n ) abrangendo um conjunto muito amplo de álgebras, incluindo a maioria dos tipos e classes de álgebra atualmente estudados. O algoritmo usado foi o algoritmo de Freese cuja eficiência depende em muito da representação das álgebras e congruências. Em especial a representação de partições/congruências como um array é determinante na eficiência do cálculo das congruências principais uma vez que permite uma junção de blocos muito rápida, uma das operações mais utilizadas durante a execução do algoritmo de congruências. Além disso a representação usada não limita o âmbito geral das álgebras suportadas. No âmbito deste doutoramento vários algoritmos para o cálculo de automorfismos foram testados e a conclusão foi que o algoritmo mais promissor foi um algoritmo que usa invariantes das operações das álgebras para limitar os possíveis automorfismos da álgebra. Este algoritmo é usado na package Loops cuja implementação foi usada como guia tendo o seu âmbito sido expandido para suportar não só magmas mas qualquer álgebra do tipo (2 m, 1 n ). A implementação final dos algoritmos de automorfismos usando a abordagem de invariantes foi contribuída para a package CREAM por Choiwah Chow com base nas conclusões e no trabalho realizado no âmbito deste doutoramento. Dada a falta de referências sobre algoritmos para calcular endomorfismos, o algoritmo para calcular endomorfismos usado na package CREAM foi definido usando teoremas básicos de álgebra universal como o teorema do homomorfismo, para relacionar congruências, álgebras quocientes, subálgebras e endomorfismos. O algoritmo foi desenvolvido usando os algoritmos de congruências e automorfismos implementados, e uma aplicação denominada MACE4. O MACE4 [27] é uma aplicação de linha de comando que procura modelos finitos de fórmulas de primeira ordem. Embora o GAP seja adequado para prototipagem e implementação rápida de algoritmos, o código resultante não é muito rápido devido ao facto de ser uma linguagem interpretada. Reescrever o código em C permitiu melhorias surpreendentes que alcançaram uma melhoria de até 670 vezes do código GAP para o código C. Além disso, a integração com o MACE4 permite combinar a eficiência de algoritmos como [15], com um amplo conjunto de possibilidades fornecidas por uma ferramenta eficiente na procura por modelos finitos de fórmulas de primeira ordem, dando uma flexibilidade muito grande à package CREAM. A package CREAM é em média 20 vezes mais rápida no cálculo de congruências dos tipos de semigrupos muito limitados que são suportados pela função CongruencesOfSemigroups da package Semigroups que é a função mais abrangente em GAP para o cálculo de congruências. A única aplicação que possui um âmbito semelhante em termos de álgebras suportadas é a interface de linha de comando UACalc, mas faz isso em jython, sem beneficiar do ecossistema existente na plataforma GAP. Quando comparado com o UACalc, o package CREAM é consistentemente mais de 3 vezes mais rápido. Relativamente a automorfismos e endomorfismos, a comparação com outras bibliotecas/aplicativos é muito difícil, uma vez que o suporte é limitado principalmente a grupos e outras estruturas algébricas intimamente relacionadas com grupos. Para essas álgebras, o desempenho das packages GAP Loops e Sonata são comparáveis e às vezes melhores do que a package CREAM. Essas bibliotecas por vezes contam com o uso de teoremas específicos para essas álgebras. Mas apenas a package CREAM suporta a maioria das álgebras estudadas em álgebra convencional e moderna. Dada a importância das congruências, automorfismos e endomorfismos para o estudo de estruturas algébricas, espera-se que a package CREAM com seu desempenho e versatilidade possa ser uma ferramenta útil para a comunidade GAP e um amplo grupo de matemáticos. O código resultante está disponível como o pacote GAP CREAM que está totalmente documentado.
- Finite model enumerationPublication . Chow, Choiwah; Araújo, João; Janota, Mikoláš; Ferreira, GildaTo study and get intuition on different types of relational algebras (groups, semigroups, and their ordered versions, quasigroups, fields, rings, MV-algebras, lattices, etc.), mathematicians resort to libraries of all models, up to isomorphism, of order n (for small values of n) of the classes of algebras they are interested in. These libraries allow experimentation such as forming and/or testing conjectures etc., to gain insights into the classes of algebras in question. Since an isomorphism partitions the set of all models into equivalence classes, so, only one representative element in each equivalence class is needed. The rest of them are redundant and are removed to make it easy to discern the structure of the algebras. To construct these libraries, we need first to find all models up to isomorphism of the classes of algebras of interest. Enumerating all finite models from first-order formulas up to isomorphism is a hard problem, even for algebras of small orders. The current best practice of finite model enumeration is to divide the job into two steps: first generate models according to the laws laid down by the first-order formula defining the class of algebra, then in the post-processing step, find only one representative model of each equivalence class of isomorphic models. An algebra of finite order n defined by a first-order formula can be represented by operation tables (also known as multiplication tables) of finite sizes. Traditional finite model enumerators such as Mace4 basically perform combinatorial search on these operation tables to find instances that satisfy, or equivalently, not violate, the rules laid down by the first-order formula. This is a hard problem. For example, there are n n 2 possible binary operation tables of size n × n with n possible values in each cell. That is, even to enumerate all models of order 4 defined with just one binary operation in its first-order formula, we are facing the task of checking 4 4 2 ≈ 4.3 billion possibilities. Traditional finite model enumerators also produce a lot of isomorphic models to the extent that isomorphism models often constitute over 99% of the outputs. This is a characteristics of algebras definable by FOL: any permutation on the domain elements of a model is a model. Finding non-isomorphic models is very computationally intensive. If we follow a simple brute-force approach, then, given m models, it may require in the worst case m(m −1)/2 comparisons of models to check for isomorphism. Each comparison of models of order n may require in the worst case n! checks because there are n! different permutations on n symbols. Thus, both of these two steps (generating models from FOL and removing isomorphic models) are resource-intensive. They prompt us to find better algorithms that also make optimal use of the available computing resources. The matter is further complicated by the fact that while modern-day generalpurpose computers are predominantly multi-core, harnessing parallelism for combinatorial search is surprisingly difficult. In this thesis, we propose the isomorphic cubes removal algorithm and the parallel cubes search algorithm to improve the speed of the traditional finite model enumerator. Searching the operation tables can be seen as searching a search tree. Any partial branch from the root (called a cube) can be searched in parallel with other branches, making full use of the computing resources available. Furthermore, some (isomorphic) cubes produce isomorphic models and hence only one of them needs to be searched. Removing isomorphic cubes not only speeds up the search process, but also reduces the number of isomorphic models that need to be removed in the post-processing step. These parallel algorithms are very scalable: more cubes can be generated if more computing resources are available. They also cope with big problems well: longer cubes are possible with higher orders of algebra; with longer cubes, more isomorphic cubes can be removed. To speed up the isomorphic models removal process, we propose the parallel invariant-based isomorphic model removal algorithms. We note that models with different sets of invariant vectors (ordered list of invariants) cannot be isomorphic. We put models into blocks in a hash-table using invariant vectors as the keys. Models across different blocks thus have different sets of invariant vectors and hence cannot be isomorphic. These blocks of models can be checked for isomorphism separately in parallel. The improvement in speed comes from (1) smaller block size means fewer pairs of models to compare for isomorphism, (2) the blocks can be processed in parallel, making full use of the computing resources available. These algorithms also cope with big problems well: models of higher orders give more different invariant vectors to spread out the models. These algorithms together often give an improvement of orders of magnitude in the performance of the traditional finite model enumerators. Better yet, these algorithms can be incorporated in many common finite model enumerators with minimal change in their code base. Furthermore, the proposed algorithms are proved to be correct. In any mathematical research, humans are the most important factor to be given considerations. Not all mathematicians are computer experts, and not all of them want to invest their valuable time in the tools of mathematics. Thus, the tools must be designed to be user-friendly, without a steep learning curve for the user to be able to use the tools effectively. We therefore develop a GAP package generator to automatically generate GAP package for algebras of small orders. The generator hides the technical details of the generation process, but gives users the ability to control many of the non-technical aspects such as the name and the definition (in FOL) of the algebra to be explored. The GAP package generator makes extensive use of the facilities provided by the GAP system, and the generated package complies with the latest GAP standards. A separate, standalone GAP package, Magmaut, is developed to provide functions to manipulate isomorphism and automorphism for algebras of type (2 m, 1 n). It supplements the generated GAP package of algebra of small orders with isomorphism-related functionality. With the tools provided by this project, mathematicians can generate the GAP packages of algebras of type (2 m, 1 n) of their interest, without being bogged down by the complexity that often comes with the tools that generate such GAP packages. In this thesis, we propose many parallel algorithms to take advantage of modern-day multi-core computers to enumerate finite models. We show some important applications of these algorithms in developing GAP packages to calculate different morphisms such as isomorphism and monomorphism etc., in generating GAP packages of algebras, and in counting the number of algebras of small orders. We also develop a user-friendly tool to help mathematicians to generate GAP packages of algebras (of type (2 m, 1 n)) of small orders.