home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 22 gnu / 22-gnu.zip / mesch12a.zip / sparse.h < prev    next >
C/C++ Source or Header  |  1994-01-13  |  7KB  |  220 lines
  1.  
  2. /**************************************************************************
  3. **
  4. ** Copyright (C) 1993 David E. Steward & Zbigniew Leyk, all rights reserved.
  5. **
  6. **                 Meschach Library
  7. ** 
  8. ** This Meschach Library is provided "as is" without any express 
  9. ** or implied warranty of any kind with respect to this software. 
  10. ** In particular the authors shall not be liable for any direct, 
  11. ** indirect, special, incidental or consequential damages arising 
  12. ** in any way from use of the software.
  13. ** 
  14. ** Everyone is granted permission to copy, modify and redistribute this
  15. ** Meschach Library, provided:
  16. **  1.  All copies contain this copyright notice.
  17. **  2.  All modified copies shall carry a notice stating who
  18. **      made the last modification and the date of such modification.
  19. **  3.  No charge is made for this software or works derived from it.  
  20. **      This clause shall not be construed as constraining other software
  21. **      distributed on the same medium as this software, nor is a
  22. **      distribution fee considered a charge.
  23. **
  24. ***************************************************************************/
  25.  
  26.  
  27. /*
  28.     Header for sparse matrix stuff.
  29.     Basic sparse routines to be held in sparse.c
  30. */
  31.  
  32. /* RCS id: $Id: sparse.h,v 1.2 1994/01/13 05:33:36 des Exp $ */
  33.  
  34. #ifndef SPARSEH
  35.  
  36. #define SPARSEH 
  37.  
  38.  
  39. #include        "matrix.h"
  40.  
  41.  
  42. /* basic sparse types */
  43.  
  44. typedef struct row_elt    {
  45.     int    col, nxt_row, nxt_idx;
  46.     Real    val;
  47.         } row_elt;
  48.  
  49. typedef struct SPROW {
  50.     int    len, maxlen, diag;
  51.     row_elt    *elt;        /* elt[maxlen] */
  52.         } SPROW;
  53.  
  54. typedef struct SPMAT {
  55.     int    m, n, max_m, max_n;
  56.     char    flag_col, flag_diag;
  57.     SPROW    *row;        /* row[max_m] */
  58.     int    *start_row;    /* start_row[max_n] */
  59.     int    *start_idx;    /* start_idx[max_n] */
  60.           } SPMAT;
  61.  
  62. /* Note that the first allocated entry in column j is start_row[j];
  63.     This starts the chain down the columns using the nxt_row and nxt_idx
  64.     fields of each entry in each row. */
  65.  
  66. typedef struct pair { int pos;    Real val; } pair;
  67.  
  68. typedef struct SPVEC {
  69.     int    dim, max_dim;
  70.     pair    *elt;        /* elt[max_dim] */
  71.            } SPVEC;
  72.  
  73. #define    SMNULL    ((SPMAT*)NULL)
  74. #define    SVNULL    ((SPVEC*)NULL)
  75.  
  76. /* Macro for speedup */
  77. #define    sprow_idx2(r,c,hint)    \
  78.     ( ( (hint) >= 0 && (hint) < (r)->len && \
  79.        (r)->elt[hint].col == (c)) ? (hint) : sprow_idx((r),(c)) )
  80.  
  81.  
  82.  
  83. /* memory functions */
  84.  
  85. #ifdef ANSI_C
  86. int sp_get_vars(int m,int n,int deg,...);
  87. int sp_resize_vars(int m,int n,...);
  88. int sp_free_vars(SPMAT **,...);
  89. #elif VARARGS
  90. int sp_get_vars();
  91. int sp_resize_vars();
  92. int sp_free_vars();
  93.  
  94. #endif
  95.  
  96. /* Sparse Matrix Operations and Utilities */
  97. #ifndef ANSI_C
  98. extern    SPMAT    *sp_get(), *sp_copy(), *sp_copy2(),
  99.             *sp_zero(), *sp_resize(), *sp_compact();
  100. extern    double    sp_get_val(), sp_set_val();
  101. extern    VEC    *sp_mv_mlt(), *sp_vm_mlt();
  102. extern    int    sp_free();
  103.  
  104. /* Access path operations */
  105. extern    SPMAT    *sp_col_access();
  106. extern    SPMAT    *sp_diag_access();
  107. extern  int     chk_col_access();
  108.  
  109. /* Input/output operations */
  110. extern    SPMAT    *sp_finput();
  111. extern    void sp_foutput(), sp_foutput2();
  112.  
  113. /* algebraic operations */
  114. extern SPMAT *sp_smlt(), *sp_add(), *sp_sub(), *sp_mltadd();
  115.  
  116.  
  117. /* sparse row operations */
  118. extern    SPROW    *sprow_get(), *sprow_xpd(), *sprow_merge(), *sprow_mltadd(),
  119.   *sprow_resize(), *sprow_copy();
  120. extern SPROW *sprow_add(), *sprow_sub(), *sprow_smlt();
  121. extern    double    sprow_set_val();
  122. extern    void    sprow_foutput();
  123. extern    int    sprow_idx(), sprow_free();
  124.  
  125. /* dump */
  126. extern  void   sp_dump(), sprow_dump();
  127. extern  MAT  *sp_m2dense();
  128.  
  129. #else
  130. SPMAT    *sp_get(int,int,int), *sp_copy(SPMAT *),
  131.     *sp_copy2(SPMAT *,SPMAT *),
  132.     *sp_zero(SPMAT *), *sp_resize(SPMAT *,int,int),
  133.     *sp_compact(SPMAT *,double);
  134. double    sp_get_val(SPMAT *,int,int), sp_set_val(SPMAT *,int,int,double);
  135. VEC    *sp_mv_mlt(SPMAT *,VEC *,VEC *), *sp_vm_mlt(SPMAT *,VEC *,VEC *);
  136. int    sp_free(SPMAT *);
  137.  
  138. /* Access path operations */
  139. SPMAT    *sp_col_access(SPMAT *);
  140. SPMAT    *sp_diag_access(SPMAT *);
  141. int     chk_col_access(SPMAT *);
  142.  
  143. /* Input/output operations */
  144. SPMAT    *sp_finput(FILE *);
  145. void    sp_foutput(FILE *,SPMAT *), sp_foutput2(FILE *,SPMAT *);
  146.  
  147. /* algebraic operations */
  148. SPMAT *sp_smlt(SPMAT *A,double alpha,SPMAT *B),
  149.       *sp_add(SPMAT *A,SPMAT *B,SPMAT *C),
  150.       *sp_sub(SPMAT *A,SPMAT *B,SPMAT *C),
  151.       *sp_mltadd(SPMAT *A,SPMAT *B,double alpha,SPMAT *C);
  152.  
  153. /* sparse row operations */
  154. SPROW    *sprow_get(int), *sprow_xpd(SPROW *r,int n,int type),
  155.         *sprow_resize(SPROW *r,int n,int type),
  156.     *sprow_merge(SPROW *,SPROW *,SPROW *,int type),
  157.         *sprow_copy(SPROW *,SPROW *,SPROW *,int type),
  158.     *sprow_mltadd(SPROW *,SPROW *,double,int,SPROW *,int type);
  159. SPROW *sprow_add(SPROW *r1,SPROW *r2, int j0,SPROW *r_out, int type), 
  160.         *sprow_sub(SPROW *r1,SPROW *r2, int j0,SPROW *r_out, int type), 
  161.         *sprow_smlt(SPROW *r1,double alpha, int j0,SPROW *r_out, int type);
  162. double    sprow_set_val(SPROW *,int,double);
  163. int      sprow_free(SPROW *);
  164. int    sprow_idx(SPROW *,int);
  165. void    sprow_foutput(FILE *,SPROW *);
  166.  
  167. /* dump */
  168. void    sp_dump(FILE *fp, SPMAT *A);
  169. void    sprow_dump(FILE *fp, SPROW *r);
  170. MAT    *sp_m2dense(SPMAT *A,MAT *out);
  171.  
  172. #endif
  173.  
  174. /* MACROS */
  175.  
  176. #define    sp_input()    sp_finput(stdin)
  177. #define    sp_output(A)    sp_foutput(stdout,(A))
  178. #define    sp_output2(A)    sp_foutput2(stdout,(A))
  179. #define    row_mltadd(r1,r2,alpha,out)    sprow_mltadd(r1,r2,alpha,0,out)
  180. #define    out_row(r)    sprow_foutput(stdout,(r))
  181.  
  182. #define SP_FREE(A)    ( sp_free((A)),  (A)=(SPMAT *)NULL) 
  183.  
  184. /* utility for index computations -- ensures index returned >= 0 */
  185. #define    fixindex(idx)    ((idx) == -1 ? (error(E_BOUNDS,"fixindex"),0) : \
  186.              (idx) < 0 ? -((idx)+2) : (idx))
  187.  
  188.  
  189. /*  NOT USED */
  190.  
  191. /* loop over the columns in a row */
  192. /*
  193. #define    loop_cols(r,e,code) \
  194.     do { int _r_idx; row_elt *e; SPROW *_t_row;            \
  195.       _t_row = (r); e = &(_t_row->elt);                \
  196.       for ( _r_idx = 0; _r_idx < _t_row->len; _r_idx++, e++ )    \
  197.       {  code;  }  }  while ( 0 )
  198. */
  199. /* loop over the rows in a column */
  200. /*
  201. #define    loop_cols(A,col,e,code) \
  202.     do { int _r_num, _r_idx, _c; SPROW *_r; row_elt *e;        \
  203.       if ( ! (A)->flag_col )    sp_col_access((A));        \
  204.       col_num = (col);                        \
  205.       if ( col_num < 0 || col_num >= A->n )                \
  206.           error(E_BOUNDS,"loop_cols");                \
  207.           _r_num = (A)->start_row[_c]; _r_idx = (A)->start_idx[_c];    \
  208.       while ( _r_num >= 0 )  {                    \
  209.           _r = &((A)->row[_r_num]);                    \
  210.               _r_idx = sprow_idx2(_r,_c,_r_idx);            \
  211.               if ( _r_idx < 0 )  continue;                \
  212.           e = &(_r->elt[_r_idx]);    code;                \
  213.           _r_num = e->nxt_row;    _r_idx = e->nxt_idx;        \
  214.           } } while ( 0 )
  215.  
  216. */
  217.  
  218. #endif
  219.  
  220.