BeBOP Optimized Sparse Kernel Interface Library  1.0.1h
Functions

Check CSR properties. More...

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <oski/config.h>
#include <oski/common.h>
#include <oski/matrix.h>
#include <oski/CSR/module.h>

Functions

static int oski_CheckIndNonDecreasing (const oski_index_t *ptr, oski_index_t m)
 Returns 1 <==> pointers are non-decreasing.
static int oski_CheckIndexBase (const oski_index_t *ptr, const oski_index_t *ind, oski_index_t m, oski_index_t n, oski_index_t base_index)
 Returns 1 <==> indices match the specified base.
static int oski_CheckHasSortedInds (const oski_index_t *ptr, const oski_index_t *ind, oski_index_t m, oski_index_t b, int *p_has_sorted_indices)
 Returns 1 <==> column indices are, within each row, sorted.
static int oski_CheckHasUniqueInds (const oski_index_t *ptr, const oski_index_t *ind, oski_index_t m, oski_index_t n, oski_index_t b, int *p_has_unique_indices)
 Returns 1 <==> column indices are, within each row, unique.
static int oski_CheckIsUpperTriangular (const oski_index_t *ptr, const oski_index_t *ind, oski_index_t m, oski_index_t b)
 Returns 0 <==> Pattern is upper triangular, and returns the offending logical row number (1-based) otherwise.
static int oski_CheckIsLowerTriangular (const oski_index_t *ptr, const oski_index_t *ind, oski_index_t m, oski_index_t b)
 Returns 0 <==> Pattern is lower triangular, and returns the offending logical row number (1-based) otherwise.
static int oski_CheckPattern (const oski_index_t *ptr, const oski_index_t *ind, oski_index_t m, oski_index_t n, oski_index_t b, oski_inmatprop_t pattern)
 Verify that the stored part of the CSR matrix matches the specified pattern.
static int oski_CheckUnitDiagImplicit (const oski_index_t *ptr, const oski_index_t *ind, oski_index_t m, oski_index_t b, int has_unit_diag_implicit)
 Verify whether or not matrix has an implicit unit diagonal.
static int BypassCheck (void)
 Check run-time environment variable, OSKI_BYPASS_CHECK, to see whether the user wants us to skip the checking of asserted input matrix properties.
int oski_CheckCSR (const oski_index_t *ptr, const oski_index_t *ind, oski_index_t m, oski_index_t n, oski_inmatpropset_t *props)
 Verify that a CSR matrix representation satisfies asserted properties.

Detailed Description

Check CSR properties.

This module implements "efficient" (i.e., O(nnz)) checks of various asserted input matrix properties.


Function Documentation

int oski_CheckCSR ( const oski_index_t *  ptr,
const oski_index_t *  ind,
oski_index_t  m,
oski_index_t  n,
oski_inmatpropset_t props 
)

Verify that a CSR matrix representation satisfies asserted properties.

This routine verifies that the following properties, if asserted, are true:

  • Row pointer indices are non-decreasing
  • 0- or 1-based indexing and indices bound by matrix dimensions.
  • Sorted column indices
  • Unique column indices.
  • Triangular storage
  • Implicit unit diagonal (i.e., if asserted, no diagonals elements must be present).

The implementation relies on O(nnz) algorithms to verify these properties.

If any of the properties can be strengthened to improve kernel performance, then the properties are modified to reflect the stronger assertion. There are two specific examples:

  • The caller asserts that column indices are not sorted but they are.
  • The caller asserts that indices are not unique within a row but they are.
Parameters:
[in]ptrRow pointers.
[in]indColumn indices.
[in]mNumber of rows.
[in]nNumber of columns.
[in,out]propsAsserted properties.
Returns:
This routine performs a series of O(nnz) checks to verify asserted properties of the given CSR matrix pattern. If any false properties are detected, this routine returns 0. Otherwise, it returns 1. If any properties can be strengthened, the corresponding property is changed in props.
Precondition:
Pointer arguments are not NULL and dimensions are non-negative.

References BypassCheck(), oski_inmatpropset_t::has_sorted_indices, oski_inmatpropset_t::has_unique_indices, oski_inmatpropset_t::has_unit_diag_implicit, oski_inmatpropset_t::index_base, oski_CheckHasSortedInds(), oski_CheckHasUniqueInds(), oski_CheckIndexBase(), oski_CheckIndNonDecreasing(), oski_CheckPattern(), oski_CheckUnitDiagImplicit(), oski_PrintDebugMessage(), and oski_inmatpropset_t::pattern.

static int oski_CheckHasSortedInds ( const oski_index_t *  ptr,
const oski_index_t *  ind,
oski_index_t  m,
oski_index_t  b,
int *  p_has_sorted_indices 
) [static]

Returns 1 <==> column indices are, within each row, sorted.

Parameters:
[in]ptrRow pointers.
[in]indColumn indices.
[in]mNumber of rows.
[in]bBase index.
[in,out]p_has_sorted_indicesPointer to an integer which, on input, indicates the ordering property being asserted by the caller: 1 if the indices are sorted, and 0 otherwise. If equal to 0 on input but the indices are sorted, then the value pointed to is changed to 1.
Returns:
Returns 1 if the column indices are sorted or if the caller didn't think they were sorted but they are. In the latter case, also sets *p_has_sorted_indices to 1.
Precondition:
All pointer arguments are non-NULL.

References ERR_FALSE_INMATPROP, and oski_HandleError.

Referenced by oski_CheckCSR().

static int oski_CheckHasUniqueInds ( const oski_index_t *  ptr,
const oski_index_t *  ind,
oski_index_t  m,
oski_index_t  n,
oski_index_t  b,
int *  p_has_unique_indices 
) [static]

Returns 1 <==> column indices are, within each row, unique.

Parameters:
[in]ptrRow pointers.
[in]indColumn indices.
[in]mNumber of rows.
[in]nNumber of columns.
[in]bBase index.
[in,out]p_has_unique_indicesPointer to an integer which, on input, indicates the uniqueness property being asserted by the caller: 1 if the indices are unique, and 0 otherwise. If equal to 0 on input but the indices are unique, then the value pointed to is changed to 1.
Returns:
Returns 1 if the column indices are unique or if the caller didn't think they were unique but they are. In the latter case, also sets *p_has_unique_indices to 1.
Note:
This routine requires a temporary storage space of n elements. If the routine cannot malloc this space itself, it simply returns 2 without calling the error handler.
Precondition:
All pointer arguments are non-NULL.
Matrix is either 0-based or 1-based.
Column indices are legal.

References ERR_FALSE_INMATPROP, oski_Free, oski_HandleError, and oski_MallocNoError.

Referenced by oski_CheckCSR().

static int oski_CheckIndexBase ( const oski_index_t *  ptr,
const oski_index_t *  ind,
oski_index_t  m,
oski_index_t  n,
oski_index_t  base_index 
) [static]

Returns 1 <==> indices match the specified base.

Precondition:
base_index is 0 or 1
All pointer arguments are non-NULL.

References ERR_FALSE_INMATPROP, and oski_HandleError.

Referenced by oski_CheckCSR().

static int oski_CheckIndNonDecreasing ( const oski_index_t *  ptr,
oski_index_t  m 
) [static]

Returns 1 <==> pointers are non-decreasing.

Parameters:
[in]ptrRow pointers.
[in]mNumber of rows.
Returns:
1 <==> ptr[i] <= ptr[i+1], for all 0 <= i < m.

Calls the error handler and returns 0 if the non-decreasing index property cannot be verified.

References ERR_FALSE_INMATPROP, and oski_HandleError.

Referenced by oski_CheckCSR().

static int oski_CheckIsLowerTriangular ( const oski_index_t *  ptr,
const oski_index_t *  ind,
oski_index_t  m,
oski_index_t  b 
) [static]

Returns 0 <==> Pattern is lower triangular, and returns the offending logical row number (1-based) otherwise.

This implementation does not call the error handler if the pattern is not lower triangular.

Precondition:
All pointer arguments are not NULL.

Referenced by oski_CheckPattern().

static int oski_CheckIsUpperTriangular ( const oski_index_t *  ptr,
const oski_index_t *  ind,
oski_index_t  m,
oski_index_t  b 
) [static]

Returns 0 <==> Pattern is upper triangular, and returns the offending logical row number (1-based) otherwise.

This implementation does not call the error handler if the pattern is not upper triangular.

Precondition:
All pointer arguments are not NULL.

Referenced by oski_CheckPattern().

static int oski_CheckPattern ( const oski_index_t *  ptr,
const oski_index_t *  ind,
oski_index_t  m,
oski_index_t  n,
oski_index_t  b,
oski_inmatprop_t  pattern 
) [static]

Verify that the stored part of the CSR matrix matches the specified pattern.

Parameters:
[in]ptrRow pointers.
[in]indColumn indices.
[in]mNumber of rows.
[in]nNumber of cols.
[in]bBase index.
[in]patternAsserted pattern type.
Returns:
1 <==> The non-zero pattern is "consistent" with the specified pattern.
Todo:
Check symmetric and Hermitian full storage cases.
Todo:
Add symmetric/Hermitian pattern check

References ERR_FALSE_INMATPROP, MAT_HERM_FULL, MAT_HERM_LOWER, MAT_HERM_UPPER, MAT_SYMM_FULL, MAT_SYMM_LOWER, MAT_SYMM_UPPER, MAT_TRI_LOWER, MAT_TRI_UPPER, oski_CheckIsLowerTriangular(), oski_CheckIsUpperTriangular(), and oski_HandleError.

Referenced by oski_CheckCSR().

static int oski_CheckUnitDiagImplicit ( const oski_index_t *  ptr,
const oski_index_t *  ind,
oski_index_t  m,
oski_index_t  b,
int  has_unit_diag_implicit 
) [static]

Verify whether or not matrix has an implicit unit diagonal.

Parameters:
[in]ptrRow pointers.
[in]indColumn indices.
[in]mNumber of rows.
[in]bBase index (0 or 1).
[in,out]has_unit_diag_implicitAn integer specifying whether the caller believes the pattern has an implicit unit diagonal (=1) or not (=0).
Returns:
1 if the pattern is consistent with the asserted pattern, or 0 otherwise.

References ERR_FALSE_INMATPROP, and oski_HandleError.

Referenced by oski_CheckCSR().