(Comp.sys.hp48) Item: 63 by seroussi at hplred.HP.COM Author: [Gadiel Seroussi] Subj: BMXL - Binary Matrix Algebra Library Date: Sat Oct 19 1991 BMXL - Binary Matrix Algebra Library V1.8 =========================================== Appended at the end of this message are the uuencoded and ->ASC versions of a library BMXL (lib number 1314). The library contains commands for fast algebraic manipulation of binary matrices over the finite field GF(2), i.e. under scalar addition and multiplication modulo 2 (XOR, AND). These matrices and manipulations are useful in various areas of applied mathematics, including coding theory, cryptography, graph theory, and others. Gadiel Seroussi Hewlett-Packard Laboratories Palo Alto, California 1. MATRIX REPRESENTATION ===================== A binary matrix is represented by a list (we will sometimes refer to this as a COMPACT representation of the matrix, as opposed to the regular HP48 matrix representation). The first element of the list is a real number (positive integer), representing the number of rows of the matrix. The rest of the elements are binary integers, each representing a COLUMN of the matrix. Rows and columns are indexed starting from zero. Lower row indices correspond to lower significance bits in the binary columns. Thus, entry (0,0) of the matrix is the least significant bit of the first binary in the list. Example: the 4x5 binary matrix 1 0 0 1 0 M = 1 1 1 1 1 0 1 1 1 0 1 1 0 0 0 is represented by the list { 4 #Bh #Eh #6h #7h #2h }. When the matrix is square, the real number representing the number of rows may be omitted. Thus, for example, the list { #Bh #Eh #6h #7h #2h } represents the 5x5 matrix 1 0 0 1 0 M = 1 1 1 1 1 0 1 1 1 0 1 1 0 0 0 0 0 0 0 0 . *** IMPORTANT LIMITATIONS: 1. In the current version of the library, all the binary numbers in the list must be of word size 64, i.e. they must take exactly 13 bytes of memory. Lists not complying with this restriction will be rejected by the commands, with a "Bad Argument Value" error message. A command (BFIX) is provided to "repair" a non-complying list. It is recommended that binary word size be set to 64 when using the library. 2. The number of rows cannot exceed 64. The number of columns is, in principle, limited only by the amount of available memory. However, some commands will not accept matrices with more than 64 columns. The library provides commands that translate regular HP48 matrices to/from the compact binary matrix representation, so matrices can be entered using the HP48 MatrixWriter, and then converted to the compact representation. Also, "viewers" are provided to display binary matrices in the HP48 graphics environment. 2. IMPLEMENTATION ============== The library is written in a mixture of ML and system RPL. It was developed using Jan Brittenson's STAR assembler, version 1.04.4. I believe all system RPL entries used in the library are "supported" (from the HP list). A few basic ML routines, however, are not "supported" (to the best of my knowledge, there are no ML routines in the "supported" list). These include routines for saving and restoring registers, reading/writing shorts and binaries from/to the user stack, etc. The library has been extensively tested on my Rev-D HP48SX. However, no guarantees are given that it will work on yours. Approximate timings: Matrix dimensions Inversion Multiplication 20x20 0.23 s 0.18 s 50x50 1.00 s 0.64 s For comparison, for the same 20x20 matrix (interpreted as a real matrix), inversion on the HP48 takes 34.3 seconds. 3. DISCLAIMERS =========== This software is provided as is, without any warranty or assertion of fitness for any purpose. This library makes use of undocumented and unsupported features of the HP48. This might cause data loss or even hardware damage. Use it at your own risk. Although I do work for Hewlett-Packard, the library was developed mostly on my free time, and I have no relation with the Corvallis Division that makes the calculator. They do not support, or even know about this package. This software is placed in the public domain. It can be copied and distributed freely, as long as (1) the package or any part of it are not included in any package sold for profit, (2) all documentation and credits are preserved. 4. LIBRARY COMMANDS ================ 4.1 Notation -------- The following notation will be used in the stack diagrams for the commands: %n - a real number n. %0/1 - a real number valued 0/1. #0/1 - a binary integer valued 0/1. #b - a binary integer. {M} - a compact binary matrix, of dimensions r x c. When several input argument combinations are possible for a command, the corresponding stack diagrams will be labeled (a), (b), (c), etc. 4.2 Commands -------- ABOUTBMX Displays current version, credits. BIDN %n -> {M} Generates an identity matrix of order n. BZERO (a) %n -> {M} (b) { %n } -> {M} (c) { %r %c } -> {M} Generates (a,b) a zero matrix of order n, or (c) a zero matrix of dimensions rxc. BRAND (a) %k -> #b (b) { %n } -> {M} (c) { %r %c } -> {M} Generates (a) a k-bit random binary number, (b) a nxn random binary matrix, or (c) a rxc random binary matrix. BMSHOW {M} -> {M} Displays a binary matrix under the Graphics environment in "scrolling" mode. Leaves the matrix unchanged on the stack. *** The number of columns must be <= 64. BTSHOW {M} -> {M} Like BMSHOW, but displays the transpose of the binary matrix. The number of columns of the input matrix is not limited. Leaves the input matrix unchanged on the stack. BVSHOW #b %n -> #b Displays a binary integer as a binary row vector in the Graphics environment. The number of bits displayed is %n. The binary integer is left on the stack. The row vector will be displayed with a "row index" of 0 to its left. This zero is not part of the vector. BTOM {M} -> Real Array Converts a compact binary matrix to a regular HP48 2-dimensional array. MTOB Real Array -> {M} Converts a regular HP48 2-dimensional array to a compact binary matrix. All nonzero entries are converted to 1. BADD {M} {M} -> {M} Adds two binary matrices. Addition is bitwise XOR. BMXM {M} {M} -> {M} Multiplies two binary matrices. BINV {M} -> {M} 1 {M} -> 0 Computes the inverse of a binary matrix, if it exists. Returns the inverse in level 2, and a real 1 in level 1 if the matrix is nonsingular, or a real 0 in level 1 otherwise. BTMX {M} -> {M'} Computes the transpose of a binary matrix. BMXV {M} #b -> #b Multiplies a binary matrix by a binary column vector. The column vector is represented by the binary #b, and it is assumed to be of dimension equal to the number of columns of the matrix. BVXM #b {M} -> #b Multiplies a binary row vector by a binary matrix. The row vector is represented by the binary #b, and it is assumed to be of dimension equal to the number of rows of the matrix. BRNK {M} -> %k Computes the rank of a binary matrix. BSOLV {M} #y -> #x Solves the linear equation M*x = y, where x and y are binary column vectors, if a solution exists (notice: only one solution will be found, even when many exist). BGAUS {M} -> {M1} #v %k Performs Gaussian elimination on the columns of M. Returns a nonsingular matrix M1, of dimensions c x c, such that M*M1 has unit vectors in rows corresponding to a maximal set of linearly independent rows of M. The binary #v has ones in positions corresponding to the same set of rows. %k is the rank of M. If M is nonsingular, M1 is the inverse of M. BNUL {M} -> {M1} Computes a basis for the null space of the rows of M. M1 is a binary matrix of dimensions s x r and rank s, where s = r - rank(M), and M1*M = 0. BDIMS {M} -> { %r %c } Return the dimensions of a binary matrix M. BGET (a) #b %k -> %0/1 (b) {M} %j -> #b (c) {M} { %i } -> #v (d) {M} { %i %j } -> %0/1 Returns the value of (a) the k-th bit of a binary integer, (b) the j-th column #b of a binary matrix, (c) the i-th row #v of a binary matrix, or (d) the value of the (i,j)-th entry of a binary matrix. *** NOTE: All indices start from zero. Valid indices are 0 <= i <= r-1, 0 <= j <= c-1. BPUT (a) #b %k %0/1 -> #b (b) #b %k #0/1 -> #b (c) {M} %j #b -> {M1} (d) {M} { %i } #v -> {M1} (e) {M} { %i %j } %0/1 -> {M1} (f) {M} { %i %j } #0/1 -> {M1} Overwrites (a, b) the k-th bit of a binary integer, (c) the j-th column of a binary matrix, (d) the i-th row of a binary matrix, or (e, f) the value of the (i,j)-th entry of a binary matrix. *** NOTE: All indices start from zero. Valid indices are 0 <= i <= r-1, 0 <= j <= c-1. BFIX {list} -> {M} "Fixes" a list that has binaries of lengths other than 16 nibbles (64 bits), but is otherwise a valid binary matrix. Also, inserts the number of rows if it was not in the list (the number of rows is assumed to be equal to the number of columns). BTRIM {M} -> {list} Deletes the number of rows from a binary matrix, if it was there. *** NOTE: Does not check that the matrix is square.