Goto Chapter: Top 1 2 3 4 5 Bib Ind
 [Top of Book]  [Contents]   [Previous Chapter]   [Next Chapter] 

5 Extended MTX (MTXE) File Format
 5.1 General information
 5.2 Example MTXE files

5 Extended MTX (MTXE) File Format

5.1 General information

The code supports reading matrices from an MTX file using ReadMTXE and writing new MTX file using WriteMTXE functions. Below a description of the format is given.

5.1-1 Representation of field elements via integers

Every finite field is isomorphic to a Galois field F=\mathop{\rm GF}(q), where q is a power of a prime, q=p^m.

Either definition requires that the primitive polynomial be specified. By default, GAP uses Conway polynomials to represent field elements. For details, as well as a large collection of Conway polynomials, please see the web page maintained by Frank Luebeck [L\t21].

In the actual file format, three different and mutually exclusive storage options for elements of an extension field can in be used.

5.1-2 Matrix storage format

There are two recommended storage formats.

1. For CSS matrices stored in separate files, the MTX header should use the integer type, with matrix elements stored in the usual order.

2. For general stabilizer codes, or to store both CSS matrices in a single file, the MTX header should use the complex type. In this case the block matrix (A,B) is stored as a complex matrix A+iB.

In both format versions, the number of columns specified in the file coincides with the code length.

Two additional matrix format versions supported by ReadMTXE and WriteMTXE are provided for compatibility. Here, the columns a_i and b_i in the blocks A and B are listed individually, and are either intercalated [the ordering (a_1, b_1, a_2,b_2,\ldots,a_n,b_n)] or are separated into column blocks (a_1,\ldots,a_n,b_1,\ldots,b_n). In both cases the number of columns in the matrix stored is twice the code length.

The ordering of the columns is governed by a parameter pair, optional in the function ReadMTXE and required in WriteMTXE.

By default, pair=0 corresponds to type=integer and pair=3 corresponds to type=complex. It is strongly recommended that matrices intended for use by others should only use these two variants of the MTXE format.

For efficiency reasons, the function DistRandStab (4.1) assumes the generator matrix with intercalated columns.

5.1-3 Explicit format of each line

The first line must have the following form:

%%MatrixMarket matrix coordinate `type` general

with type either integer or complex.

The second line is optional and specifies the field, the primitive polynomial used (in the case of an extension field), and the storage format of field elements.

 Field: `field` PrimitiveP(x): `polynomial` Format: `format`

Here the records should be separated by one or more spaces; while field, polynomial, and format should not contain any spaces. Any additional records in this line will be silently ignored.

The field option should specify a valid field, GF(q) or GF(p^m), where q>1 should be a power of the prime p.

The polynomial should be a valid expanded monic polynomial with integer coefficients, with a single independent variable x; it should contain no spaces. An error will be signaled if polynomial is not a valid primitive polynomial of the field. This argument is optional; if not specified, one may assume that the Conway polynomial should be used.

The optional format string should be "AdditiveInt" (the default for prime fields), "PowerInt" (currently the default for extension fields with m>1) or "VectorInt".

The primitive polynomial must be written explicitly as x^m+a_{m-1}*x^{m-1}+\ldots+a_1*x+a_0, where the integer coefficients a_i will be interpreted modulo p. The primitive polynomial should not contain any spaces.

% Field: GF(`q`) PrimitiveP(x): `polynomial` 

For example, with q=5^2, the Conway polynomial f_{5,2}(x)=x^2-x+2, and the second line can read

% Field: GF(25) PrimitiveP(x): x^2-x+2 Format: PowerInt

The following is an equivalent form of the same polynomial and can also be used

% Field: GF(25) PrimitiveP(x): x^2+4*x+2 

The field may be left undefined; by default, it is \mathop{\rm GF}(2), or it can be specified by hand when reading the matrices. If the primitive polynomial is undefined, it will be assumed that the Conway polynomial used internally by GAP should be used.

Next follows the comment section, with each line either empty or starting with the % symbol:

% Example of the comment line

After the comment section, in agreement with MTX format, goes the line giving the dimensions of the matrix and the number of non-zero elements:

rows     columns     `(number of non-zero elements)`

Then all non-zero elements are listed as three or four integers according to the type:

i     j     element[i,j]
i     j     a[i,j]     b[i,j]

Notice that column and row numbers must start with 1, as prescribed in the original MTX format.

5.1-4 Matrix Storage Implementation Details

Neither the WriteMTXE nor ReadMTXE currently support the Format: parameter. Prime field elements are only stored "as is", i.e., as integers to be taken modulo p, while extension field elements are only stored in the PowerInt format, i.e., with the power of the primitive element specified, or "-1" for zero.

The function WriteMTXE can only save field elements with the primitive polynomial used internally by GAP, i.e., the Conway polynomial.

The function ReadMTXE can read matrix elements specified (in the case of an extension field) with any primitive polynomial as specified in the file.

Given the field \mathop{\rm GF}(p^m) and the primitive polynomial p(x) specified in the file, the function ReadMTXE first checks that the degree of p(x) is indeed m and that it is a primitive polynomial in the corresponding prime field \mathop{\rm GF}(p). If either of these tests fail, ReadMTXE produces an error. Otherwise, it will attempt to find the conversion coefficient c such that \alpha^c is a root of p(x), starting with c=1. When found, the multiplicative inverse s such that sc\equiv 1\bmod (q-1) will be used to convert the elements being read, i.e., for any matrix element y read, y^s will be used instead.

Notice that, unless the Conway polynomial was used (in which case c=s=1, and the conversion is trivial), this search can be slow for large fields, as all integer values in [1,2,\ldots,q-2] will be tested sequentially. To help ensure that the correct polynomial is used, it is recommended that orthogonality of matrices be checked.

5.2 Example MTXE files

In this section we give two sample MTXE files storing the stabilizer generator matrix of 5-qubit codes.

First, matrix (with one redundant linearly-dependent row) stored with type=integer and pair=1 (intercalated columns [a_1,b_1,a_2,b_2,\ldots]) is presented. Notice that the number of columns is twice the actual length of the code. Even though the field is specified explicitly, this matrix would work with any prime field.

%%MatrixMarket matrix coordinate integer general                
% Field: GF(7)
% 5-qubit code generator matrix / normal storage with intercalated cols
5 10 20
1 1 1
1 4 1
1 6 -1
1 7 -1
2 3 1
2 6 1
2 8 -1
2 9 -1
3 1 -1
3 5 1
3 8 1
3 10 -1
4 2 -1
4 3 -1
4 7 1
4 10 1
5 2 1
5 4 -1
5 5 -1
5 9 1

This same matrix is stored in the file matrices/n5k1A.mtx. This is how the matrix can be read and distance calculated:

gap>         filedir:=DirectoriesPackageLibrary("QDistRnd","matrices");;
gap>     lis:=ReadMTXE(Filename(filedir,"n5k1A.mtx" ));;
gap>     Print("field ",lis[1],"\n");
field GF(7)
gap>     dist:=DistRandStab(lis[3],100,0 : field:=lis[1]);

The same matrix can also be stored with type=complex and pair=3 (complex pairs [a_1+i b_1,a_2+i b_2,\ldots]). In this format, the number of columns equals the code length.

%%MatrixMarket matrix coordinate complex general
% works with any prime field
% 5-qubit code generator matrix / normal storage with intercalated cols
% [[5,1,3]]_p
4 5 16
1 1 1 0
1 2 0 1
1 3 0 -1
1 4 -1 0
2 2 1 0
2 3 0 1
2 4 0 -1
2 5 -1 0
3 1 -1 0
3 3 1 0
3 4 0 1
3 5 0 -1
4 1 0 -1
4 2 -1 0
4 4 1 0
4 5 0 1

The matrix above is written in the file matrices/n5k1.mtx. To calculate the distance, we need to specify the field [unless we want to use the default binary field].

gap>     lis:=ReadMTXE(Filename(filedir,"n5k1.mtx" ));;
gap>     Print("field ",lis[1],"\n");
field GF(2)
gap>     dist:=DistRandStab(lis[3],100,0,2 : field:=lis[1]);
gap>     q:=17;;
gap>     lis:=ReadMTXE(Filename(filedir,"n5k1.mtx") : field:= GF(q));;
gap>     Print("field ",lis[1],"\n");
field GF(17)
gap>     dist:=DistRandStab(lis[3],100,0,2 : field:=lis[1]);

Finally, the following is an example of a five-qudit code over \mathop{\rm GF}(2^3) constructed by the script examples/cyclic.g.

%%MatrixMarket matrix coordinate complex general
% Field: GF(2^3) PrimitiveP(x): x^3+x+1
% code [[5,1,3]]_8
% cyclic w=4 x^6+Z(2^3)^4*x^5+Z(2^3)^4*x^3+Z(2)^0
% Powers of GF(8) primitive element and -1 for Zero are given
5 5 20
1 1 0 -1
1 2 -1 4
1 3 -1 4
1 4 0 -1
2 2 0 -1
2 3 -1 4
2 4 -1 4
2 5 0 -1
3 1 0 -1
3 3 0 -1
3 4 -1 4
3 5 -1 4
4 1 -1 4
4 2 0 -1
4 4 0 -1
4 5 -1 4
5 1 -1 4
5 2 -1 4
5 3 0 -1
5 5 0 -1
 [Top of Book]  [Contents]   [Previous Chapter]   [Next Chapter] 
Goto Chapter: Top 1 2 3 4 5 Bib Ind

generated by GAPDoc2HTML