testvec.c File Reference

Detailed Description

Code to generate vectors and vector views for testing and off-line benchmarking.

#include <config/config.h>
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include "abort_prog.h"
#include "array_util.h"
#include "testvec.h"
#include "rand_util.h"
#include "parse_opts.h"

Routines to display parameter values on stderr.

-----------------------------------------------------

static void DisplayValue (const char *name, oski_value_t x)
static void DisplayMatop (const char *matname, oski_matop_t op)
static void DisplayVecView (const char *name, const oski_vecview_t x)
static void DisplayATAop (const char *matname, oski_ataop_t op)

Defines

#define MIN(a, b)   ((a) < (b) ? (a) : (b))
 Macro to return the minimum value of a pair.

Typedefs

typedef int(* filter_funcpt )(oski_index_t m, oski_index_t n, oski_index_t i, oski_index_t j)
 Defines a 'non-zero filter' function type.

Functions

oski_vecview_t testvec_Create (oski_index_t len, oski_index_t num_vecs, oski_storage_t orient, int use_minstride)
 Allocate a dense 2-D array, fill it with random values, and return it wrapped in a newly allocated vector view object.
size_t testvec_CalcDataSize (const oski_vecview_t x)
 Based on its storage orientation and stride, returns the minimum size (in elements) of the underlying storage array.
oski_vecview_t testvec_Clone (const oski_vecview_t x)
 Clone an object created using testvec_Create().
void testvec_Destroy (oski_vecview_t x)
 Destroy a test vector created via testvec_Create().
void testmat_GenDenseCSR (oski_index_t m, oski_index_t n, oski_index_t **p_ptr, oski_index_t **p_ind, oski_value_t **p_val)
 Generates a dense, non-symmetric matrix in sparse CSR format.
size_t testmat_ChooseDim (size_t nz_volume, size_t elem_size)
 Select the dimension for a square, dense matrix whose size in Bytes exceeds nz_volume.
size_t ChooseDivisible (size_t n, size_t d)
 Returns the smallest integer $n' >= n$ such that $d | n'$.
void testmat_ChangeSizeDenseCSR (oski_index_t m_new, oski_index_t n_new, oski_index_t *ptr, oski_index_t *ind)
 Changes the dimensions (and pattern) of a previously allocated dense CSR test matrix.
void testmat_ChangeSizeDenseTriCSR (oski_index_t n_new, int make_lower, int cond_for_trisolve, oski_index_t *ptr, oski_index_t *ind, oski_value_t *val)
 Changes the pattern of a previously allocated dense CSR test matrix to a dense triangular pattern.
static oski_index_t gcd (oski_index_t a, oski_index_t b)
static oski_index_t lcm (oski_index_t a, oski_index_t b)
void testmat_GenBlockedBandedCSR (oski_index_t k_min, oski_index_t row_min, oski_index_t r, oski_index_t c, oski_index_t *p_n, oski_index_t **p_ptr, oski_index_t **p_ind, oski_value_t **p_val)
 Generates a matrix with a banded shape, where each row contains dense blocks of a given size.
static int CheckMatMultVectors (const oski_matrix_t A, const oski_vecview_t x, const oski_vecview_t y0, const oski_vecview_t y1)
 Returns 0 if two distinct computations of a matrix-vector product are numerical 'equal' within some reasonable error bound, or ERR_WRONG_ANS otherwise.
int check_MatMult_instance (const oski_matrix_t A0, const oski_matrix_t A1, oski_matop_t opA, oski_value_t alpha, const oski_vecview_t x, oski_value_t beta, oski_vecview_t y0)
 Check an instance of matrix-vector multiply.
int check_MatTrisolve_instance (const oski_matrix_t A0, const oski_matrix_t A1, oski_matop_t opA, oski_value_t alpha, const oski_vecview_t b)
 Check an instance of sparse triangular solve.
int check_MatMultAndMatTransMult_instance (const oski_matrix_t A0, const oski_matrix_t A1, oski_value_t alpha, const oski_vecview_t x, oski_value_t beta, oski_vecview_t y0, oski_matop_t opA, oski_value_t omega, const oski_vecview_t w, oski_value_t zeta, oski_vecview_t z0)
 Check and instance of simultaneous multiplication by sparse $A$ and $\mathrm{op}(A)$.
int check_MatTransMatMult_instance (const oski_matrix_t A0, const oski_matrix_t A1, oski_ataop_t opA, oski_value_t alpha, const oski_vecview_t x, oski_value_t beta, oski_vecview_t y0, oski_vecview_t t0)
 Check an instance of sparse $A^TAx$.
static int filter_valid (oski_index_t m, oski_index_t n, oski_index_t i, oski_index_t j)
 A filter that allows any valid entry to be a non-zero.
static int filter_strictly_lower_tri (oski_index_t m, oski_index_t n, oski_index_t i, oski_index_t j)
 Filter for a strictly lower triangular matrix.
static int filter_strictly_upper_tri (oski_index_t m, oski_index_t n, oski_index_t i, oski_index_t j)
 Filter for a strictly upper triangular matrix.
static int filter_diagonal (oski_index_t m, oski_index_t n, oski_index_t i, oski_index_t j)
 Filter for diagonal entries.
static int filter_offdiag (oski_index_t m, oski_index_t n, oski_index_t i, oski_index_t j)
 Filter for off-diagonal entries.
static int filter_lower_tri (oski_index_t m, oski_index_t n, oski_index_t i, oski_index_t j)
 Filters a lower triangular matrix.
static int filter_upper_tri (oski_index_t m, oski_index_t n, oski_index_t i, oski_index_t j)
 Filters a upper triangular matrix.
static void create_rawmat_csr (oski_index_t m, oski_index_t n, oski_index_t min_nnz_row, oski_index_t max_nnz_row, filter_funcpt filter, oski_index_t **p_ptr, oski_index_t **p_ind, oski_value_t **p_val)
 Create a raw CSR matrix, using 0-based indices, with a bounded number of non-zeros per row.
static void adjust_base (oski_index_t *array, oski_index_t len, oski_index_t b)
 Given an array of index pointers, adjust the base index.
static void expand_rawmat_csr (oski_index_t **p_ptr, oski_index_t **p_ind, oski_value_t **p_val, oski_index_t m, oski_index_t n, oski_inmatprop_t shape)
 Expands a raw, 0-based CSR matrix into a full-storage 0-based CSR matrix if shape == MAT_SYMM_FULL or MAT_HERM_FULL.
oski_matrix_t testmat_GenRandomCSR (oski_index_t m, oski_index_t n, oski_index_t min_nnz_row, oski_index_t max_nnz_row, oski_inmatprop_t shape, int implicit_diag, int index_base, oski_copymode_t copymode, oski_index_t **p_ptr, oski_index_t **p_ind, oski_value_t **p_val)
 Create a raw matrix pattern and matrix object corresponding to the caller-specified dimensions and shape.
static void GetShapeBounds (oski_inmatprop_t shape, oski_index_t m, oski_index_t i, oski_index_t *p_j_min, oski_index_t *p_j_max)
 Returns the minimum and maximum non-zero column index for a given row of an m x m triangular matrix with the prescribed shape (lower or upper triangular).
void testmat_GenTriCSC (oski_index_t m, oski_index_t max_nnz_row, oski_inmatprop_t shape, int is_unitdiag, int is_sorted, int indbase, oski_index_t **p_ptr, oski_index_t **p_ind, oski_value_t **p_val)
 Generates a random, well-conditioned sparse triangular matrix in CSC format with the prescribed attributes for testing triangular solve.
void testmat_GenTriCSR (oski_index_t m, oski_index_t max_nnz_row, oski_inmatprop_t shape, int is_unitdiag, int is_sorted, int indbase, oski_index_t **p_ptr, oski_index_t **p_ind, oski_value_t **p_val)
 Generates a random, well-conditioned sparse triangular matrix in CSR format with the prescribed attributes for testing triangular solve.

Typedef Documentation

typedef int(* filter_funcpt)(oski_index_t m, oski_index_t n, oski_index_t i, oski_index_t j)
 

Defines a 'non-zero filter' function type.

A non-zero filter function f(m, n, i, j) returns 1 if (i, j) is an 'acceptable' non-zero for a matrix of size m x n, or 0 otherwise. The indices (i, j) are assume to be 1-based.

For instance, the following is a composition of two filter functions that can be used to generate a lower triangular matrix:

int
filter_any( oski_index_t m, oski_index_t n,
            oski_index_t i, oski_index_t j )
{
    // Ensures valid indices
    return (1 <= i) && (i <= m) && (1 <= j) && (j <= n);
}

int
filter_lowertri( oski_index_t m, oski_index_t n,
                 oski_index_t i, oski_index_t j )
{
  return filter_any(m, n, i, j) && j <= i;
}

Function Documentation

int check_MatMult_instance (  const oski_matrix_t  A0,
const oski_matrix_t  A1,
oski_matop_t  opA,
oski_value_t  alpha,
const oski_vecview_t  x,
oski_value_t  beta,
oski_vecview_t  y0
) 
 

Check an instance of matrix-vector multiply.

If the calculation is merely incorrect, then this routine prints a message and returns ERR_WRONG_ANS.

int check_MatMultAndMatTransMult_instance (  const oski_matrix_t  A0,
const oski_matrix_t  A1,
oski_value_t  alpha,
const oski_vecview_t  x,
oski_value_t  beta,
oski_vecview_t  y0,
oski_matop_t  opA,
oski_value_t  omega,
const oski_vecview_t  w,
oski_value_t  zeta,
oski_vecview_t  z0
) 
 

Check and instance of simultaneous multiplication by sparse $A$ and $\mathrm{op}(A)$.

If the calculation is merely incorrect, then this routine prints a message and returns ERR_WRONG_ANS.

int check_MatTransMatMult_instance (  const oski_matrix_t  A0,
const oski_matrix_t  A1,
oski_ataop_t  opA,
oski_value_t  alpha,
const oski_vecview_t  x,
oski_value_t  beta,
oski_vecview_t  y0,
oski_vecview_t  t0
) 
 

Check an instance of sparse $A^TAx$.

If the calculation is merely incorrect, then this routine prints a message and returns ERR_WRONG_ANS.

int check_MatTrisolve_instance (  const oski_matrix_t  A0,
const oski_matrix_t  A1,
oski_matop_t  opA,
oski_value_t  alpha,
const oski_vecview_t  b
) 
 

Check an instance of sparse triangular solve.

If the calculation is merely incorrect, then this routine prints a message and returns ERR_WRONG_ANS.

static int CheckMatMultVectors (  const oski_matrix_t  A,
const oski_vecview_t  x,
const oski_vecview_t  y0,
const oski_vecview_t  y1
)  [static]
 

Returns 0 if two distinct computations of a matrix-vector product are numerical 'equal' within some reasonable error bound, or ERR_WRONG_ANS otherwise.

Parameters:
[in] A A sparse matrix, $A$.
[in] x A vector, $x$.
[in] y0 The matrix-vector product $\alpha A x$ computed using one algorithm, where $\alpha$ is some scalar.
[in] y1 The matrix-vector product $\alpha A x$ computed using another algorithm.
Returns:
0 if $y_0$ and $y_1$ are numerically equivalent to within round-off error, given that two different algorithms were used to compute $y_0$ and $y_1$.

static void create_rawmat_csr (  oski_index_t  m,
oski_index_t  n,
oski_index_t  min_nnz_row,
oski_index_t  max_nnz_row,
filter_funcpt  filter,
oski_index_t **  p_ptr,
oski_index_t **  p_ind,
oski_value_t **  p_val
)  [static]
 

Create a raw CSR matrix, using 0-based indices, with a bounded number of non-zeros per row.

This routine aborts the program if a memory error occurs.

static void expand_rawmat_csr (  oski_index_t **  p_ptr,
oski_index_t **  p_ind,
oski_value_t **  p_val,
oski_index_t  m,
oski_index_t  n,
oski_inmatprop_t  shape
)  [static]
 

Expands a raw, 0-based CSR matrix into a full-storage 0-based CSR matrix if shape == MAT_SYMM_FULL or MAT_HERM_FULL.

Note:
This implementation just duplicates all the non-zeros in their transpose position, so column indices will not be unique.

static void GetShapeBounds (  oski_inmatprop_t  shape,
oski_index_t  m,
oski_index_t  i,
oski_index_t *  p_j_min,
oski_index_t *  p_j_max
)  [static]
 

Returns the minimum and maximum non-zero column index for a given row of an m x m triangular matrix with the prescribed shape (lower or upper triangular).

Parameters:
[in] shape MAT_TRI_LOWER or MAT_TRI_UPPER.
[in] m Matrix dimension.
[in] i Row index (0-based).
[out] p_j_min Pointer to variable in which to hold the minimum non-zero column index (0-based).
[out] p_j_max Pointer to variable in which to hold the maximum non-zero column index (0-based).
Returns:
Returns the minimum and maximum bounds on the non-zero column index. Aborts the program if 'shape' is invalid. Does not store any result in *p_j_min (or *p_j_max) if it is NULL.

void testmat_ChangeSizeDenseCSR (  oski_index_t  m_new,
oski_index_t  n_new,
oski_index_t *  ptr,
oski_index_t *  ind
) 
 

Changes the dimensions (and pattern) of a previously allocated dense CSR test matrix.

Parameters:
[in] m_new New number of rows.
[in] n_new New number of columns.
[in,out] ptr Prior row pointers.
[in,out] ind Prior index values.
Returns:
A new pattern for a dense m_new x n_new matrix in sparse CSR format, conforming to the following specifications:
  • It is stored in CSR format.
  • It uses 0-based indexing.
  • Indices are sorted and unique.
This routine assumes that ptr, ind were previously allocated to be sufficiently large to store a dense matrix of the requested size. The previous contents of (ptr, ind) are ignored.

void testmat_ChangeSizeDenseTriCSR (  oski_index_t  n_new,
int  make_lower,
int  cond_for_trisolve,
oski_index_t *  ptr,
oski_index_t *  ind,
oski_value_t *  val
) 
 

Changes the pattern of a previously allocated dense CSR test matrix to a dense triangular pattern.

Parameters:
[in] n_new New dimension.
[in] make_lower Set to any non-zero value to generate a lower triangular matrix; otherwise, this routine generates an upper-triangular pattern.
[in] cond_for_trisolve Set to any non-zero value to generate random values that lead to a well-conditioned triangular system solve; otherwise, put all values in the range [0, 1].
[in,out] ptr Prior row pointers.
[in,out] ind Prior index values.
[in,out] val Prior non-zero values.
Returns:
A new pattern for a dense triangular n_new x n_new matrix in sparse CSR format, conforming to the following specifications:
  • It is stored in CSR format.
  • It uses 0-based indexing.
  • Indices are sorted and unique.
  • The value of all diagonal elements is O(1), pure real, and all off-diagonal elements are O(1/n_new).
This routine assumes that ptr, ind were previously allocated to be sufficiently large to store a dense matrix of the requested size. The previous contents of (ptr, ind, val) are ignored.

size_t testmat_ChooseDim (  size_t  nz_volume,
size_t  elem_size
) 
 

Select the dimension for a square, dense matrix whose size in Bytes exceeds nz_volume.

Parameters:
[in] nz_volume Minimum desired size of matrix data array, in Bytes.
[in] elem_size Size of each matrix element value.
Returns:
The dimension of a square dense matrix whose size (volume, in bytes) is at least nz_volume.

void testmat_GenBlockedBandedCSR (  oski_index_t  k_min,
oski_index_t  row_min,
oski_index_t  r,
oski_index_t  c,
oski_index_t *  p_n,
oski_index_t **  p_ptr,
oski_index_t **  p_ind,
oski_value_t **  p_val
) 
 

Generates a matrix with a banded shape, where each row contains dense blocks of a given size.

Parameters:
[in] k_min Minimum number of non-zeros.
[in] row_min Minimum number of non-zeros per row.
[in] r Row block size.
[in] c Column block size.
[in,out] p_m Pointer to scalar in which to store the number of rows.
[in,out] p_n Pointer to scalar in which to store the number of columns.
[in,out] p_ptr Pointer to row pointers.
[in,out] p_ind Pointer to column indices.
[in,out] p_val Pointer to values.

void testmat_GenDenseCSR (  oski_index_t  m,
oski_index_t  n,
oski_index_t **  p_ptr,
oski_index_t **  p_ind,
oski_value_t **  p_val
) 
 

Generates a dense, non-symmetric matrix in sparse CSR format.

Parameters:
[in] m Logical number of matrix rows. Must be positive.
[in] n Logical number of matrix columns. Must be positive.
[in,out] p_ptr Pointer to a pointer in which to return the newly allocated row pointers.
[in,out] p_ind Pointer to a pointer in which to return the newly allocated column indices.
[in,out] p_val Pointer to a pointer in which to return the newly allocated non-zero values.
Returns:
Newly allocated 3-array storage in (*p_ptr, *p_ind, *p_val). On error, aborts the application with an error message.
The newly created matrix has the properties specified in testmat_ChangeSizeDenseCSR().

Todo:
What is the best way to initialize the dense matrix? For benchmarking, it seems sufficient to initialize all entries to 'tiny' values (here, $\frac{1}{\max{m}{n}}$), which is faster than calling the random number generator.

oski_matrix_t testmat_GenRandomCSR (  oski_index_t  m,
oski_index_t  n,
oski_index_t  min_nnz_row,
oski_index_t  max_nnz_row,
oski_inmatprop_t  shape,
int  implicit_diag,
int  index_base,
oski_copymode_t  copymode,
oski_index_t **  p_ptr,
oski_index_t **  p_ind,
oski_value_t **  p_val
) 
 

Create a raw matrix pattern and matrix object corresponding to the caller-specified dimensions and shape.

Parameters:
[in] m Number of rows.
[in] n Number of columns.
[in] min_nnz_row Minimum # of non-zeros per row.
[in] max_nnz_row Maximum # of non-zeros per row. If max_nnz_row is less than min_nnz_row, then it is taken to be n.
[in] shape Matrix shape (MAT_GENERAL ... MAT_HERM_FULL).
[in] implicit_diag Set to 1 if the diagonal should be unit and implicit, or 0 otherwise.
[in] index_base Set to 1 or 0 to set the base index.
[in,out] p_ptr Pointer to buffer to hold the row pointers, or NULL if none is desired.
[in,out] p_ind Pointer to buffer to hold the column indices, or NULL if none is desired.
[in,out] p_val Pointer to buffer to hold the stored non-zero values, or NULL if none is desired.
Returns:
On success, returns a valid matrix handle and sets (*p_ptr, *p_ind, *p_val) to point to the raw CSR representation. Otherwise, aborts the program.
Note:
If p_ptr, p_ind, or p_val are NULL but the copy mode is set to SHARE_INPUTMAT, then there is the potential for a memory leak.

void testmat_GenTriCSR (  oski_index_t  m,
oski_index_t  max_nnz_row,
oski_inmatprop_t  shape,
int  is_unitdiag,
int  is_sorted,
int  indbase,
oski_index_t **  p_ptr,
oski_index_t **  p_ind,
oski_value_t **  p_val
) 
 

Generates a random, well-conditioned sparse triangular matrix in CSR format with the prescribed attributes for testing triangular solve.

Parameters:
[in] m Dimension of the desired matrix.
[in] max_nnz_row Maximum desired number of non-zeros per row.
[in] shape MAT_TRI_LOWER or MAT_TRI_UPPER.
[in] is_unitdiag Set to 0 if the matrix should have
[in] indbase Index base, 0 or 1. an implicit unit diagonal, or non-zero otherwise.
[in] is_sorted Set to any non-zero value if the column indices should be sorted in increasing order.
[in,out] p_ptr Pointer in which to store a newly allocated array of row pointers for the matrix, or NULL if not desired.
[in,out] p_ind Pointer in which to store a newly allocated array of column indices for the matrix, or NULL if not desired.
[in,out] p_val Pointer in which to store a newly allocated array of non-zero values, or NULL if not desired.

oski_vecview_t testvec_Create (  oski_index_t  len,
oski_index_t  num_vecs,
oski_storage_t  orient,
int  use_minstride
) 
 

Allocate a dense 2-D array, fill it with random values, and return it wrapped in a newly allocated vector view object.

Parameters:
[in] len Length of a column vector.
[in] num_vecs Number of column vectors.
[in] orient Storage orientation.
[in] use_minstride Set to 0 to choose the minimum possible stride for the specified orientation, or 1 to choose a slightly larger stride with perturbation chosen at random.
Returns:
A test vector conforming to the caller's request.

Generated on Wed Sep 19 16:41:23 2007 for BeBOP Optimized Sparse Kernel Interface Library by  doxygen 1.4.6