convert.c File Reference

Detailed Description

CSR-to-CB format conversion routines.

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <stdarg.h>
#include <oski/config.h>
#include <oski/common.h>
#include <oski/matcreate.h>
#include <oski/modloader.h>
#include <oski/matrix.h>
#include <oski/tune.h>
#include <oski/CSR/format.h>
#include <oski/CB/format.h>
#include <oski/CB/module.h>
#include <oski/xforms_internal.h>

Defines

#define MIN(a, b)   ((a) < (b) ? (a) : (b))
 Return the minimum of two values.

Functions

static int ExpandSymm (const oski_matCSR_t *mat, const oski_matcommon_t *props, oski_matCSR_t **p_mat_full)
static oski_index_t CountZeroRows (oski_index_t m, const oski_index_t *ptr)
 Returns the number of rows of the CSR matrix A that are structurally zero.
static oski_index_t FindFirstNonzeroRow (oski_index_t m, const oski_index_t *ptr, int has_unit_diag, oski_index_t i_min)
 Returns the index of the first row $i \geq i_0$ containing at least one structural non-zero, and returns $i \geq m$ if no such row can be found.
static oski_index_t FindMinColIndex (oski_index_t m, oski_index_t n, const oski_index_t *ptr, const oski_index_t *ind, oski_index_t b, oski_index_t has_unit_diag, oski_index_t i_start, oski_index_t i_max, oski_index_t j_min)
 Returns the smallest column $j \geq j_0$ of any structural non-zero in the $r$ consecutive rows beginning at row $i_0$, $j \geq n$ if no such non-zero can be found.
static oski_index_t FindFirstNzRowInSubmat (oski_index_t m, const oski_index_t *ptr, const oski_index_t *ind, oski_index_t b, int has_unit_diag, oski_index_t i0, oski_index_t j0, oski_index_t i_max, oski_index_t j_max)
static oski_index_t FindNextZeroRowInSubmat (oski_index_t m, const oski_index_t *ptr, const oski_index_t *ind, oski_index_t b, int has_unit_diag, oski_index_t i0, oski_index_t j0, oski_index_t i_max, oski_index_t j_max)
static int FindSubblock (oski_index_t m, const oski_index_t *ptr, const oski_index_t *ind, oski_index_t b, int has_unit_diag, oski_index_t i_min, oski_index_t j_min, oski_index_t i_max, oski_index_t j_max, oski_index_t *p_i_start, oski_index_t *p_i_max)
static void SetupBlockRowPtrs (const oski_index_t *ptr, const oski_index_t *ind, oski_index_t b, int has_unit_diag, oski_index_t i_start, oski_index_t j_min, oski_index_t R, oski_index_t j_max, oski_index_t *bptr)
static void CopyValues (const oski_index_t *ptr, const oski_index_t *ind, const oski_value_t *val, oski_index_t b, int has_unit_diag, oski_index_t i_start, oski_index_t j_min, oski_index_t R, oski_index_t j_max, const oski_index_t *bptr, oski_index_t *bind, oski_value_t *bval)
static int ConvertSubblock (const oski_index_t *ptr, const oski_index_t *ind, const oski_value_t *val, oski_index_t b, int has_unit_diag, oski_index_t i_start, oski_index_t j_min, oski_index_t i_max, oski_index_t j_max, simplelist_t *cache_blocks)
static int MakeSparseSubblocks (oski_index_t m, oski_index_t n, const oski_index_t *ptr, const oski_index_t *ind, const oski_value_t *val, oski_index_t b, int has_unit_diag, oski_index_t i0, oski_index_t j0, oski_index_t i_max, oski_index_t j_max, simplelist_t *cache_blocks)
 Recursive procedure to convert a specified submatrix of a CSR matrix into a sequence of CSR subblocks consisting of consecutive non-zero rows.
static int MakeBlock (oski_index_t m, oski_index_t n, const oski_index_t *ptr, const oski_index_t *ind, const oski_value_t *val, oski_index_t b, int has_unit_diag, oski_index_t i0, oski_index_t j0, oski_index_t i_max, oski_index_t j_max, simplelist_t *cache_blocks)
 Convert a specified submatrix of a CSR matrix into a single cache block.
static int ConvertToCSR (oski_index_t m, oski_index_t n, const oski_index_t *ptr, const oski_index_t *ind, const oski_value_t *val, oski_index_t b, int has_unit_diag, oski_index_t min_row, oski_index_t min_col, oski_index_t R, oski_index_t C, simplelist_t *cache_blocks)
 Recursive procedure to compute a cache block partitioning of an $m\times n$ matrix $A$, stored in CSR format.
static oski_index_t FindMinColsBegin (oski_index_t n, const oski_index_t *ptr, const oski_index_t *ind, oski_index_t b, int has_unit_diag, oski_index_t i_start, oski_index_t i_max, oski_index_t j_min, oski_index_t *k_begin)
static void FindMaxCols (const oski_index_t *ptr, const oski_index_t *ind, oski_index_t b, int has_unit_diag, oski_index_t i_start, oski_index_t i_max, oski_index_t j_start, oski_index_t j_max, const oski_index_t *k_begin, oski_index_t *k_end)
static oski_index_t FindMinColsContinue (oski_index_t n, const oski_index_t *ptr, const oski_index_t *ind, oski_index_t b, int has_unit_diag, oski_index_t i_start, oski_index_t i_max, oski_index_t j_min, oski_index_t *k_begin)
static void SetupBlockRowPtrs_Sorted (const oski_index_t *ptr, const oski_index_t *ind, oski_index_t b, int has_unit_diag, oski_index_t i_start, oski_index_t j_min, oski_index_t R, oski_index_t j_max, const oski_index_t *k_begin, const oski_index_t *k_end, oski_index_t *bptr)
static void CopyValues_Sorted (const oski_index_t *ptr, const oski_index_t *ind, const oski_value_t *val, oski_index_t b, int has_unit_diag, oski_index_t i_start, oski_index_t j_min, oski_index_t R, oski_index_t j_max, const oski_index_t *k_begin, const oski_index_t *k_end, const oski_index_t *bptr, oski_index_t *bind, oski_value_t *bval)
static int ConvertSubblock_Sorted (const oski_index_t *ptr, const oski_index_t *ind, const oski_value_t *val, oski_index_t b, int has_unit_diag, oski_index_t i_start, oski_index_t j_min, oski_index_t i_max, oski_index_t j_max, const oski_index_t *k_begin, const oski_index_t *k_end, simplelist_t *cache_blocks)
static int MakeBlock_Sorted (const oski_index_t *ptr, const oski_index_t *ind, const oski_value_t *val, oski_index_t b, int has_unit_diag, oski_index_t i0, oski_index_t j0, oski_index_t i_max, oski_index_t j_max, const oski_index_t *k_begin, const oski_index_t *k_end, simplelist_t *cache_blocks)
 Convert a specified submatrix of a CSR matrix into a single cache block, assuming sorted column indices.
static int ConvertToCSR_Sorted (oski_index_t m, oski_index_t n, const oski_index_t *ptr, const oski_index_t *ind, const oski_value_t *val, oski_index_t b, int has_unit_diag, oski_index_t min_row, oski_index_t min_col, oski_index_t R, oski_index_t C, simplelist_t *cache_blocks)
 Faster but less memory-efficient implementation of ConvertToCSR() which assumes sorted column indices.
void * oski_CreateMatReprFromCSR (const oski_matCSR_t *mat, const oski_matcommon_t *props,...)
 Method: Instantiate from an existing CSR representation.
oski_matCSR_t * oski_ConvertMatReprToCSR (const void *mat, const oski_matcommon_t *props)
 Method: Convert to CSR format.
int oski_CreateLuaMatReprFromCSR (lua_State *L)
 Matrix-type specific method to convert from a CSR matrix, with arguments passed on the Lua stack.

Function Documentation

static int ConvertToCSR (  oski_index_t  m,
oski_index_t  n,
const oski_index_t *  ptr,
const oski_index_t *  ind,
const oski_value_t *  val,
oski_index_t  b,
int  has_unit_diag,
oski_index_t  min_row,
oski_index_t  min_col,
oski_index_t  R,
oski_index_t  C,
simplelist_t *  cache_blocks
)  [static]
 

Recursive procedure to compute a cache block partitioning of an $m\times n$ matrix $A$, stored in CSR format.

Parameters:
[in] m Total number of rows in the matrix.
[in] n Total number of columns in the matrix.
[in] ptr Row pointers for the CSR input matrix.
[in] ind Column indices for the CSR input matrix.
[in] val Non-zero values for the CSR input matrix.
[in] b Index base of the input matrix (0 or 1).
[in] has_unit_diag Zero only if the input matrix stores the diagonal elements explicitly.
[in] min_row Minimum row index $i_0$ to consider for the current cache block (0-based index).
[in] min_col Minimum column index $j_0$ to consider for the current cache block (0-based index).
[in] R Maximum row block size.
[in] C Maximum column block size.
[in,out] cache_blocks Current list of cache blocks.
Returns:
This routine scans $A$, beginning at position $(i_0, j_0)$, for a non-zero cache block of maximum size $R\times C$. If such a cache block is found, it is appended to cache_blocks, and this procedure calls itself recursively to process the rest of the matrix. When no such cache blocks remain, this routine returns 0. This routine returns a non-zero error code on error.

static int ConvertToCSR_Sorted (  oski_index_t  m,
oski_index_t  n,
const oski_index_t *  ptr,
const oski_index_t *  ind,
const oski_value_t *  val,
oski_index_t  b,
int  has_unit_diag,
oski_index_t  min_row,
oski_index_t  min_col,
oski_index_t  R,
oski_index_t  C,
simplelist_t *  cache_blocks
)  [static]
 

Faster but less memory-efficient implementation of ConvertToCSR() which assumes sorted column indices.

This algorithm reverts to ConvertToCSR() on error.

static oski_index_t CountZeroRows (  oski_index_t  m,
const oski_index_t *  ptr
)  [static]
 

Returns the number of rows of the CSR matrix A that are structurally zero.

Todo:
This routine duplicates the functionality of oski_CountZeroRowsCSR(), and could be eliminated.

static oski_index_t FindFirstNonzeroRow (  oski_index_t  m,
const oski_index_t *  ptr,
int  has_unit_diag,
oski_index_t  i_min
)  [static]
 

Returns the index of the first row $i \geq i_0$ containing at least one structural non-zero, and returns $i \geq m$ if no such row can be found.

Parameters:
[in] m Total number of rows $m$ in the matrix.
[in] ptr Row pointers.
[in] has_unit_diag Non-zero <==> the diagonal is all ones and not stored explicitly.
[in] i_min Minimum desired row index, $i_0$.

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