An algebra calculator program

The Universal Algebra Calculator is a mathematical program. It performs computations related to general algebraic structures.

Authors:

Contents


Main features and availability

The present version has the following math functionalities:

The program has a Graphical User Interface to access these functionalities via menus. In addition, this interface provides the facilities to

The program also has a batch version that allows to

The program is available under UNIX and Microsoft Windows. It can be freely downloaded from any of the sites

http://www.cs.elte.hu/~ewkiss/software/uaprog

http://www.math.hawaii.edu/~ralph/software/uaprog

You can download the sources, and also executables for various platforms.


Recommended use

The program can be used as a teaching aid, for example to display the lattice of divisors of an integer, the lattice of normal subgroups of small groups, or to generate subgroups in small groups.

The program is especially useful in finding reasonable conjectures in Tame Congruence Theory. For example, it can find skew congruences and weird subdirectly irreducible factors in subdirect squares of an algebra. (This activity corresponds to doing experiments in natural sciences!) It is reasonable to compute the congruence lattice of an algebra of up to 200 elements (unless the lattice itself is too big). This is sufficient, because many nontrivial questions can be modeled in the subdirect squares of algebras of ten elements or less.


Conditions of use

The program is under the GNU General Public License (see the file COPYING). This essentially guarantees your rights to share and distribute the program freely, together with its source code. It forbids others to prevent you doing this (for example, by copyrighting it behind your back). It also forbids people to enhance this program and then sell this derived work for money.

If you achieve results by using this program, please make a reference to the program in the References section of your paper. We are writing a short paper about the program jointly with Matt Valeriote and whoever else contributes to it, and ask you to refer to this paper.


Getting the program

If you only want to use the program, it is sufficient to download the executables from any of the sites listed above. These are available for the following platforms.

uacalc-101_bin.zip

for Microsoft Windows, and

uacalc-1.0.1-1.i386.rpm

for Linux on Intel/AMD platforms that support rpm, and where you have root privileges.

You may also want to get the file test_algebras.zip or test_algebras.tar.gz, depending on your platform. In all other cases, you have to get the sources, and compile the program yourself. See the instructions in the section about compilation.


Installation

Download and Install the Java Runtime Environment

The program is written using the Java programming language, and some parts are written in C. To run a Java-program on any computer, you have to download the Java Runtime Environment, or JRE for short. If you download and install this environment, then you can run any Java application, not just this program.

Note that if you also want to compile Java programs, or even the C part of the present program, you have to download the Java Software Development Kit instead, which contains the JRE. See the details in the section about compilation.

There are several vendors who produced a JRE. These may differ in performance. The one provided by Sun can be downloaded from

http://www.javasoft.com/j2se

Here you can find the JRE for Solaris, Linux and Microsoft Windows, and also installation instructions.

YOU MUST DOWNLOAD VERSION 1.3.1 OF THE ENVIRONMENT for the Calculator to work normally. Please, do not use version 1.4.0 beta.

If you are using Linux, then we strongly recommend that you use instead the JRE manufactured by IBM Corporation, because that will execute the program much faster (which may be important in lengthy calculations). This is available from

http://www-106.ibm.com/developerworks/java/jdk/linux130/jre-info.html

You have to register (which is free) and fill out a form in order to download this version of the JRE. You should get version 1.3.0 (or later).

Depending on your Linux distribution, a JRE may have already been installed on your machine. If so, please make sure that its version is sufficiently recent. Make sure also that if you install the JRE that you downloaded, then it is this downloaded version that your machine uses by default.


Installation under Linux via rpm

If your Linux distribution supports the rpm Red Hat Package Manager (the most popular ones like Red Hat, SuSE do), then simply type as a superuser the following command:

rpm -ivh uacalc-1.0.1-1.i386.rpm

Make sure that the PATH (of all ordinary users) contains /usr/local/bin (by editing scripts in /etc if necessary).

Installation is now complete. Every user on your system can use the program now by switching to a directory where he wants to store the algebra files, and typing

UACalc

This must be done under XWindows.


Installation under Microsoft Windows

We assume that you want to use drive C: (but you can use any other drive, too). Copy the file uacalc-101_bin.zip to C:\, and unzip it with winzip, or with pkunzip:

C:\> pkunzip -d uacalc-101_bin.zip

This will create a subdirectory C:\UACALC. Next, make sure that your PATH contains this subdirectory. For example, type

C:\> PATH=C:\UACALC;%PATH%

You may want to put this line into your AUTOEXEC.BAT.

To run the program, open a DOS window, switch to a directory where you want to store your algebras, and type

UACALC

You need to run the program from a DOS window, because messages may be written there. The program itself will have separate windows, so do not use the DOS window in full screen mode.


Compiling the program from sources

The sources are contained in the files

uacalc-1.0.1.tar.gz

uacalc-101_src.zip

The contents of these two files are identical, only their formats differ, so grab the zip file for Windows, and the tar.gz file for UNIX. You may save some work (and money) by downloading the file

UACalc.jar

as well. You may also want to get the file test_algebras.zip or test_algebras.tar.gz, depending on your platform.

Open up these packages using

gzip -d uacalc-1.0.1.tar.gz

tar -xvf uacalc-1.0.1.tar

under UNIX, or by using winzip or pkunzip under Windows (make sure to keep the directory structure). Change to the directory

uacalc-1.0.1

under UNIX, and

uacalc-101

under Windows, respectively. That is the root of the source-tree.

Now you have to compile the Java part, and the C part.


Compiling the Java part

The result of the compilation will be a file named UACalc.jar. Therefore you can avoid this step, if you download this file (which is a binary that works on any platform).

If you want to recompile it, you need first to install the Java Software Development Kit (called JDK) for your platform (Solaris, Linux, Windows). These are available from Sun at

http://www.javasoft.com/j2se

We do NOT recommend to use the IBM version for compiling. Note that the JDK includes the JRE, so you do not have to download that separately to actually run the program. However, under Linux we still recommend to use the IBM JRE to run the program for performance reasons.

To do the compilation, the following steps have to be performed:

Under Linux, this process is aided by a script: change to the directory src and run ./compile.


Compiling the C part

To compile the C part you still need the JDK, or at least the C header files included in the JDK. Change to the directory src/C. You can find four makefiles here:

If you want to look at the code then please bear in mind that THIS IS A TEMPORARY VERSION, which we wanted to release fast so that you can use it. In later versions we may change even the most basic classes. Most of the classes are not yet documented properly in the present version. So if you want to write your own extensions, please wait until the next release, or contact us.


Using the program

The program included in this distribution has two parts: the graphical part (started by UACalc) and the batch part (started by uab, or by scripts described below). Most of the time you should probably use the graphical part. This program has a graphical user interface, and we hope that its use is self-explanatory. We shall nevertheless give some hints on how to use it below. NOTE THAT THIS GRAPHICAL PART IS NOT INTENDED TO BE RUN REMOTELY (across a network), as its graphic performance will degrade considerably.

The batch version has the advantage that it can be used without a graphical terminal (so you can log on to a fast machine and run it there). The two parts share the same data, so you can create an algebra with the graphical version, transform the files over, and do computations using the batch version.


Speed

Normally, programs written in C are 2-3 times faster than ones written in Java. The batch version is written entirely in C, the graphical part is written in Java, but uses some of the routines of the C part. However, the graphical part has improved algorithms for some of these calculations. All in all, we recommend to stick with UACalc when possible. Note that the Linux version of the graphical part is considerably faster than the Windows version (see the benchmarks below).


Data files

All data is stored on disk, both the algebras, and their computed invariants. If an invariant, like the congruence lattice, is computed, then it is stored on disk, and the next time it is read, instead of being computed. Therefore please do not manipulate these files by an editor, and do not delete them manually. Here are some tips for safely using the program.


Algebras

In the present version, all algebras are assumed to have underlying set {0,1,2,...,n-1} (where n is the size of the algebra). Thus editing and creating an algebra always consists of manipulating tables of integers. The names of the operations are also fixed, they are f0, f1, ... . Similarly, when computing the congruence lattice, the congruences are numbered from 0 to some integer in a random way. These same numbers are used when drawing the congruence lattice. Of course the program makes it possible to view the partition corresponding to any given congruence. In a later release we hope to provide symbolic names for objects (like elements of an algebra, or tuples, congruences, etc.).


How to use the batch part

You have to use the graphical part to create and edit algebras. When that is done, and you have an algebra saved, then you can quit the program UACalc (if you want), and use the following batch commands:
centr: compute centrality
cg: generate a congruence
fact: create a factor algebra
min: compute minimal sets (used in Tame Congruence Theory)
p1: compute all unary (and idempotent unary) polynomials
pra: create a direct product
prc: create a product congruence
spr: generate a subalgebra in a direct power
typ: compute a congruence lattice, and its TCT labeling.

Type these commands without arguments to get help on how to use them. Note that cg and typ are not recommended to use, because the graphical part does these calculations much faster. Also fact and pra are not time-critical. You do not gain time by using the batch version of the commands centr, min, p1, spr, because the graphical part uses the same C routines as the batch part to do these calculations.


Test algebras and benchmarks

The file test_algebras.zip (or test_algebras.tar.gz) contains some example algebras which you may use to test the program, or to learn how to use it. Look at the *.dat files for a description of what is interesting in them. We call your attention to w4.alg, which is a 6 element algebra whose congruence lattice contains all five TCT types, and so it is worth displaying it to get familiar with the colors!

The algebra b2 is a two element primal algebra, and so the congruence lattice of its seventh direct power, b2_7, is isomorphic to a 128 element boolean algebra. This congruence lattice, together with is type labeling has been computed in

on a 366 MHz AMD K6-2 processor with a 66 MHz FSB.


Mathematical references

In order to use the basic features of the program, you should be aware of the rudiments of general algebra. There is a textbook that we recommend:

S. Burris, H. P. Sankappanavar: A course in Universal Algebra.

It can be freely downloaded from

http://www.thoralf.uwaterloo.ca/htdocs/ualg.html

To understand the TCT-related features, you should consult the book

D. Hobby, R. McKenzie: The structure of finite algebras.


Hints for using the graphical part

Editing is dangerous!

Do not be surprised that when you bring up the Algebra Editor, then the main frame of the program becomes dead, and remains dead until you close the editor. This is to prevent you to start any calculations on an algebra being edited. In later versions we may relax this restriction somewhat with a better locking mechanism. Please note however that when you edit an algebra, then all results computed so far about that algebra become invalid. The program therefore deletes this data when you finish editing. If you want to keep this data, then use the Save As menu when saving an edited existing algebra for the first time, and select a new name.


Check the tables!

When creating a new operation, the program lists all possible arguments, and asks you to fill in the corresponding value. It is difficult not to make an error while doing this. Even if you realize that you made an error, do not stop! Fill in all values, and then go to the Change values menu. This lets you edit (and check) the table of the operation, and then you can correct the mistakes.


Hit enter when finished editing a cell!

When you edit a value of an operation, then the new value you entered is not accepted by the program until you hit Enter. Even if you save while editing a cell, the old value is saved! You can press Escape to cancel editing a cell. On the other hand, moving to another cell with Tab or the arrow keys confirms the new value in the cell. The Tab key is especially useful when entering values fast (for example, when entering generators of subpowers).


Stopping calculations

The Compute/Stop menu lets you stop calculations. This facility is not implemented yet for all possible calculations. When a calculation is stopped, the program informs you about this. During some calculations the program gives you a progress report (like: there are already 20000 congruences, or: it will take at least 1000 more hours to finish this calculation). These are the times to use the Stop menu.


The Congruence Displayer

The most important part of the program is the Congruence Displayer, which comes up when you use the Compute/Congruences menu.

Do not always compute the congruence lattice. Originally the congruence lattice is not computed. There are algebras, where this may not even be feasible to do. For example, if you have a set of 10 elements, and no operations, then the congruence lattice is too big to be computed, but it may still be possible to compute other invariants, like the TCT type set of the algebra. Even when the congruence lattice is not computed you can

You can compute the congruence lattice of the algebra by using the Lattice/Compute and Label menu. Then the displayer window extends itself. Let us explain the four boxes that appear. These are the MODE box (top left), the LIST box (top right), the COVER MODE box (bottom left) and the COVER LIST box (bottom right). All boxes can be opened by clicking on them, and you can make a selection in each of them. The contents of the boxes depend on each other in this order.

The MODE box lets you decide if you want to see

Whichever of these you select, the list of the corresponding congruences appears in the LIST box. Thus, for example, if you are hunting for large subdirectly irreducible factors, then select meet-irreducibles in the MODE box, and then browse the contents of the LIST box to find a congruence with many classes.

The LIST box has one selected congruence (the one displayed when the box is closed). The COVER LIST box shows either all the upper covers or all the lower covers of this selected congruence, depending on the two states of the COVER MODE box.

For example, suppose that you want to compute the minimal sets for the cover C3 -< C15. Then

Now at the right bottom corner you can already see the TCT type of this quotient. The Taming/Minimal sets menu will compute the minimal sets for this cover.

If there are many congruences, you may find it more convenient to use the Select menu to select congruences instead of trying to locate them in the LIST box.

Math calculations. You can compute meets and joins via the Lattice menu, and Centrality with the Centrality menu. See the paper

K. A. Kearnes, E. W. Kiss: Finite Algebras of Finite Complexity

(that appeared in Discrete Mathematics) for the meaning of weak and rectangular centrality.


The Lattice Drawer

If the congruence lattice is not too big, then we recommend that you draw it graphically, using the Graphics/Drawer menu. This brings up a new window, where the lattice is drawn. Hit the Improve button to get a better picture, unless the lattice is too big.

The colors of the edges correspond to the TCT labeling:

Here are two hints to remember the colors: the richer types are lighter, and the solvable types have a red component.

The Drawer works in coordination with the Displayer. The selected congruence is highlighted (currently has a thick magenta border), its displayed covers are green rather than black, and the selected cover is thicker than the others. When you make a selection in the MODE box, the corresponding congruences are highlighted. You can change the selected congruence and the selected edge by right-clicking on the corresponding point or edge.

If the lattice is big, you may want to draw only an interval. Click the Interval button, and then select the desired bottom with a left click, and the desired top by a right click. You must do this in such a way that the selected bottom element is strictly below the selected top element. Then click OK to get a drawing of this interval. You can use all the features described above on the drawn interval with the exception that selection in the MODE box provides no highlighting (the Displayer still "displays" the entire lattice). You can select several intervals, and switch between them with the buttons on the right of the Drawer.


Troubleshooting

Error messages

It may happen that upon startup the program complains about missing fonts, or about the inability to provide VirtualBinding for certain keyboard keys. These are harmless messages (and signify problems with the JRE, not with the program). You should ignore these messages unless you have problems running the program itself.

PLEASE MAIL ANY OTHER PROBLEMS, REQUESTS TO

Emil W. Kiss: ewkiss@cs.elte.hu

Please do so even if you solved the corresponding problem. This helps us to improve the program, or the documentation. We may be able to to assemble a FAQ from your remarks. Also please inform us about successful/unsuccessful installations, etc.


Line ending characters

The files generated by the program have the usual platform dependent line ending characters. This may make editing difficult (but the program edit under Windows, and emacs under UNIX handles these problems properly). We tried to make sure that the program reads the files created on other platforms, so you can transfer algebras from one computer to another.


Mailing list

You can subscribe to a mailing list in order to get information, and participate in discussions concerning the following topics.

The address of the list is uaprog-l@matrix.newpaltz.edu. The automatic way to subscribe is to send email to Majordomo@matrix.newpaltz.edu. Please, include the line

subscribe uaprog-l

in the body of the message (preferably as the first line; the subject of the letter is not processed). If you include the line

help

then you get usage information concerning the list (for example, you can learn how to retrieve the archive containing all previous correspondence).


History and acknowledgments

The first version of the program has been written by students of Matt Valeriote in 1988-91, for XWindows. This version had many of the features of the present program, and some additional ones, too, which we plan to implement. These include working with terms and identities, drawing subalgebra lattices, etc. However that version has many bugs. It is available from

ftp://icarus.math.mcmaster.ca:/pub/UA/Algebra.tar.gz

Many of the ideas for writing the present program came from that version. This old version had some partial MS-DOS ports, but these are now made obsolete by the present program.

The other source of inspiration has been Ralph Freese's lattice drawing program, which is integrated into the present program. It can display any lattice, not just congruence lattices. You can try out the original version online, or download the source. The address is

http://www.math.hawaii.edu/~ralph/LatDraw

The program makes use of Ralph Freese's algorithms concerning partitions, to speed up calculations. You can download the corresponding reprints from

http://www.math.hawaii.edu/~ralph/papers.html


Back to the top