The Universal Algebra Calculator is a mathematical program. It performs computations related to general algebraic structures.
Authors:
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.
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.
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.
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.
for Microsoft Windows, and
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.
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
Here you can find the JRE for Solaris, Linux and Microsoft Windows, and also installation instructions.
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.
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.
The sources are contained in the files
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
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.
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
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:
javac command to compile all files
named *.java in all subdirectories of
src/uacalc and src/javamath;
jar command to create
UACalc.jar from the resulting classes.
Under Linux, this process is aided by a script: change to
the directory src and run ./compile.
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:
Makefile.linux is for normal Linux
installations. It assumes that you installed the JDK in
/usr/local/jdk1.3.1. If not, edit the second
line of this makefile accordingly. Then type
make -f Makefile.linux
This produces two files: uab and
libua.so. Now switch back to the root of the
source-tree, where you can find two scripts,
InstallAsRoot and
InstallAsUser. Run the first one as a superuser
if you have root privileges. If you don't, you can still
install the program locally by running
InstallAsUser (which will install it into the
bin subdirectory of your home directory). Make sure that
your PATH contains /usr/local/bin
(for Root installs) and $HOME/bin (for User
installs). You can uninstall the program using the
Uninstall* scripts in this directory.
Makefile.solaris is for installation under
Solaris. You will have to edit the JDK_ROOT
variable near the top of the file to point to the location
of your JDK installation. Otherwise every step is the same
as above. This makefile assumes that you use the GNU
C-compiler GCC. If not, you have to do further
editing.
Makefile.Borland_windows is to compile the
C part using the free Borland Command-line C++
Compiler (which can be downloaded from
http://www.borland.com/bcppbuilder/freecompiler
after registering, which is free). This compiler includes a
make utility, too. To compile, type
make -f Makefile.Borland_windows
in the src/C subdirectory of the
source-tree. Then, to install the program, create a
subdirectory C:\UACALC, and copy the files
uab.exe, ua.dll,
*.bat to C:\UACALC. Then copy
UACalc.jar to C:\UACALC. Finally
change to the root of the source-tree and copy
UACalc.bat to C:\UACALC. Set your
PATH, and you are done.
Makefile.linux_dynamic is not intended for
novice users. It is similar to Makefile.linux,
but links the executable uab dynamically, and
therefore requires that the shared library
libua.so be configured using
ldconfig. See the file
src/install_lib.
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.
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.
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).
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.
z2, then all data related to this algebra are
contained in files named z2.*. (The operation
tables are in z2.alg, the congruences are in
z2.con, etc.) When you create a new algebra
(like a subpower or a factor), then you have to give it a
new name (like z2_2 for its direct square). It
is safe to delete all related files (like deleting
z2.*). The program itself has a menu that does
this. However, in this case the deleted algebras are saved
under names like z2.*.bak. So you can still
recover accidentally deleted data. Thus it is safe to delete
all files *.bak, too.
*.log. However, these may contain details of
calculations that are not displayed on the screen. Normally
these details are not needed, but sometimes they help
understanding the behavior of an algebra.
copy
z2.*, and not just z2.alg. If you fear
that the computed data is inconsistent (say after a system
crash, or if you pulled the plug on the program), then try
to copy z2.alg, z2.lck and
z2.dat, and discard the rest of
z2.*. If this still has problems, just keep
z2.alg.
z2.dat contains textual
information about the algebra z2. You can enter
text freely when you create the algebra, and the main
results of later calculations are written to this
file. There is a menu which lets you display the contents of
this file. However, you can also look at this file by any
other tool, and you can even edit this file if you want to
enter some crucial information you want to remember later,
this is safe.
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.).
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.
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.
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. Sankappanawar: 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.
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.
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.
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).
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 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.
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.
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.
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.
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).
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