3.1.4.3 Two dimensional arrays

Several other functions in ‘matcon.h’ are meant to support conversions between matrices represented as lists of lists and arrays in a variety of representations. Dense matrices either square or rectangular are accommodated, and symmetric square matrices can be stored with redundant entries omitted in either upper trangular or lower triangular format.

Similarly to the vector operations (One dimensional arrays) these functions are intended to allow a developer to present an interface to external libraries based on lists rather than arrays.

The preferred convention for virtual code applications is to represent a matrix as a list of lists of entities (typically numbers), with one list for each row of the matrix. For example, a 3 by 3 matrix containing a value of aij in the i-th row and the j-th column would be represented by this list of three lists.

<
   <a11,a12,a13>,
   <a21,a22,a23>,
   <a31,a32,a33>>

Such a representation is convenient for manipulation by virtual machine combinators, for example transpose (Transpose), and is readily identified with the matrix it represents.

If a matrix is symmetric (that is, with aij equal to aji for all values of i and j), only the lower triangular portion needs to be stored because the other entries are redundant. The list representatation would be something like this.

<
   <a11>,
   <a21,a22>,
   <a31,a32,a33>>

Another alternative for representing a symmetric matrix is to store only the upper triangular portion. In this case, a list such as the following would be used.

<
   <a11,a12,a13>,
   <a22,a23>,
   <a33>>

The upper and lower triangular representations are distinguishable by whether or not the row lengths form an increasing sequence.

In addition to representing symmetric matrices, these upper and lower triangular forms are also appropriate for representing matrices whose remaining entries are zero, such as the factors in an LU decomposition.

Function: void *avm_matrix_of_list (int square, int upper_triangular, int lower_triangular, int column_major, list operand, size_t item_size, list *message, int *fault)

This function converts a matrix in one of the list representations above to a contiguous array according to the given specifications. The array can contain elements of any fixed sized type of size item_size. The memory for it is allocated by this function and it should be freed by the caller when no longer needed.

The input matrix is given by the list parameter, operand, and its format is described by the integer parameters square, upper_triangular, and lower_triangular. The number of bytes occupied by each entry is given by item_size.

To the extent these specifications are redundant, they are used for validation. If any of the following conditions is not met, the integer referenced by fault is assigned a non-zero value and a copy of the message <'bad matrix specification'> represented as a list is assigned to the list referenced by message. Errors are also possible due to insufficient memory.

• The operand must be a list of lists of lists such that each item of each item is has a length of item_size, and its items consist of character representations as required by avm_value_of_list (Primitive types).
• If the lengths of the top level lists in the operand form an increasing sequence, the lower triangular representation is assumed and the lower_triangular parameter must have a non-zero value.
• If the lengths of the top level lists in the operand form a decreasing sequence, the upper triangular representation is assumed and the upper_triangular parameter must have a non-zero value.
• At least one of upper_triangular or lower_triangular must be zero.
• If square has a non-zero value, then either all items of the operand must have the same length as the operand, or if it’s triangular, then the longest one must have the same length as the operand.
• If the operand is neither square nor a triangular form, all items of it are required to have the same length.

The parameters upper_triangular or lower_triangular may be set to non-zero values even if the operand is not in one of the upper or lower triangular forms discussed above. In this case, the operand must be square or rectangular (i.e., with all items the same length), and the following interpretations apply.

• If upper_triangular is non-zero, the diagonal elements and the upper triangular portion of the input matrix are copied to the output. The lower triangle of the input is ignored and the lower triangle of the output is left uninitialized.
• If lower_triangular is non-zero, the diagonal elements and the lower triangular portion of the input matrix are copied to the output. The upper triangle of the input is ignored and the upper triangle of the output is left uninitialized.

The column_major parameter affects the form of the output array. If it is zero, then each row of the input matrix is stored in a contiguous block of memory in the output array, and if it is non-zero, each column is stored contiguously. The latter representation is also known as Fortran order and may be required by library functions written in Fortran.

In all cases when a triangular form is specified, part of the output matrix is left uninitialized. The redundant entries may be assigned if required by the avm_reflect_matrix function (Related utility functions).

Function: list avm_list_of_matrix (void *matrix, int rows, int cols, size_t item_size, int *fault)

This function performs an inverse operation to avm_matrix_of_list by taking the address of a matrix stored as a contiguous array in the parameter matrix and constructing the list representation as discussed above. Only square and rectangular matrices in row major order are supported, but see avm_matrix_transposition for a way to convert between row major and column major order (Related utility functions).

The parameters rows, cols, and item_size describe the form of the matrix. The list returned as a result will have a length of rows, and each item will be a list of length cols. Each item of the result corresponds to a row of the matrix, and each item of the items represents the an entry of the matrix as a list of length item_size. These items could be passed to avm_value_of_list, for example, to obtain their values (Primitive types).

Memory is allocated by this function to create the list, which can be reclaimed by avm_dispose (Simple Operations). If there is insufficient memory, the integer referenced by fault is assigned a non-zero value and the result returned is a list representation of the message <'memory overflow'>. The error message be reclaimed by the caller as well using avm_dispose.

A packed storage representation for symmetric square matrices and triangular matrices is of interest because it is used by some library functions, notably those in LAPACK, to save memory and thereby accommodate larger problems. In this representation, column major order is assumed, and either the lower or the upper triangle of the matrix is not explicitly stored. For example, a lower triangular matrix whose list representation corresponds to

<
   <a11>,
   <a21,a22>,
   <a31,a32,a33>,
   <a41,a42,a43,a44>>

would be stored according to the memory map

[a11 a21 a31 a41 a22 a32 a42 a33 a43 a44]

with a11 at the beginning address. An upper triangular matrix

<
   <a11,a12,a13,a14>,
   <a22,a23,a24>,
   <a33,a34>,
   <a44>>

would be stored according to the memory map

[a11 a12 a22 a13 a23 a33 a14 a24 a34 a44].

A couple of functions converting between list representations and packed array format are provided as described below.

Function: void *avm_packed_matrix_of_list (int upper_triangular, list operand, int n, size_t item_size, list *message, int *fault)

If the operand is a list in one of the triangular forms explained above, then the upper_triangular parameter must be consisitent with it, being non-zero if the operand is upper triangular and zero otherwise.

If the operand is not in a triangular form, then each item of the operand must be a list of length n. In this case, the upper_triangular parameter indicates which triangle of the operand should be copied to the result, and the other triangle is ignored.

In either case, the operand must have a length of n, and the items of its items must be lists of length item_size containing character representations as required by avm_value_of_list (Primitive types).

If the input parameters are inconsistent or if there is insufficient memory to allocate the result, the integer referenced by fault is assigned a non-zero value, and the list referenced by message is assigned a copy of the list representation of <'bad matrix specification'> or <'memory overflow'>, respectively. A non-empty message must be reclaimed by the caller using avm_dispose (Simple Operations).

If there are no errors, the result is a pointer to a packed array representation of the operand as explained above. The memory for this result is allocated by this function and should be freed by the caller when no longer required. The number of bytes allocated will be item_size * (n * (n + 1))/2.

Function: list avm_list_of_packed_matrix (int upper_trianguler,void *operand, int n, size_t item_size, int *fault)

This function performs an inverse operation to that of avm_packed_matrix_of_list given the address of a packed matrix stored according to one of the memory maps discussed above. The operand parameter holds the address, the parameter n gives the number of rows, and the upper_triangular parameter specifies which of the two possible memory maps to assume.

If there is sufficient memory, the result returned is a list in one of the triangular forms described above, being upper triangular if the upper_triangular parameter is non-zero, with values of length item_size taken from the array.

In the event of a memory overflow, the integer referenced by fault is assigned a non-zero value and the result is a copy of the message <'memory overflow'> represented as a list. A segmentation fault is possible if this function is passed an invalid pointer or dimension.

This document was generated on December 10, 2012 using texi2html 1.82.