home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 22 gnu / 22-gnu.zip / mesch12a.zip / sparse.c < prev    next >
C/C++ Source or Header  |  1994-01-13  |  25KB  |  1,029 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.   Sparse matrix package
  28.   See also: sparse.h, matrix.h
  29.   */
  30.  
  31. #include    <stdio.h>
  32. #include    <math.h>
  33. #include        <stdlib.h>
  34. #include    "sparse.h"
  35.  
  36.  
  37. static char    rcsid[] = "$Id: sparse.c,v 1.8 1994/01/13 05:32:38 des Exp $";
  38.  
  39. #define    MINROWLEN    10
  40.  
  41.  
  42.  
  43. /* sp_get_val -- returns the (i,j) entry of the sparse matrix A */
  44. double    sp_get_val(A,i,j)
  45. SPMAT    *A;
  46. int    i, j;
  47. {
  48.    SPROW    *r;
  49.    int    idx;
  50.    
  51.    if ( A == SMNULL )
  52.      error(E_NULL,"sp_get_val");
  53.    if ( i < 0 || i >= A->m || j < 0 || j >= A->n )
  54.      error(E_SIZES,"sp_get_val");
  55.    
  56.    r = A->row+i;
  57.    idx = sprow_idx(r,j);
  58.    if ( idx < 0 )
  59.      return 0.0;
  60.    /* else */
  61.    return r->elt[idx].val;
  62. }
  63.  
  64. /* sp_set_val -- sets the (i,j) entry of the sparse matrix A */
  65. double    sp_set_val(A,i,j,val)
  66. SPMAT    *A;
  67. int    i, j;
  68. double    val;
  69. {
  70.    SPROW    *r;
  71.    int    idx, idx2, new_len;
  72.    
  73.    if ( A == SMNULL )
  74.      error(E_NULL,"sp_set_val");
  75.    if ( i < 0 || i >= A->m || j < 0 || j >= A->n )
  76.      error(E_SIZES,"sp_set_val");
  77.    
  78.    r = A->row+i;
  79.    idx = sprow_idx(r,j);
  80.    /* printf("sp_set_val: idx = %d\n",idx); */
  81.    if ( idx >= 0 )
  82.    {    r->elt[idx].val = val;    return val;    }
  83.    /* else */ if ( idx < -1 )
  84.    {
  85.       /* Note: this destroys the column & diag access paths */
  86.       A->flag_col = A->flag_diag = FALSE;
  87.       /* shift & insert new value */
  88.       idx = -(idx+2);    /* this is the intended insertion index */
  89.       if ( r->len >= r->maxlen )
  90.       {
  91.      r->len = r->maxlen;
  92.      new_len = max(2*r->maxlen+1,5);
  93.      if (mem_info_is_on()) {
  94.         mem_bytes(TYPE_SPMAT,A->row[i].maxlen*sizeof(row_elt),
  95.                 new_len*sizeof(row_elt));
  96.      }
  97.  
  98.      r->elt = RENEW(r->elt,new_len,row_elt);
  99.      if ( ! r->elt )    /* can't allocate */
  100.        error(E_MEM,"sp_set_val");
  101.      r->maxlen = 2*r->maxlen+1;
  102.       }
  103.       for ( idx2 = r->len-1; idx2 >= idx; idx2-- )
  104.     MEM_COPY((char *)(&(r->elt[idx2])),
  105.          (char *)(&(r->elt[idx2+1])),sizeof(row_elt));
  106.       /************************************************************
  107.     if ( idx < r->len )
  108.     MEM_COPY((char *)(&(r->elt[idx])),(char *)(&(r->elt[idx+1])),
  109.     (r->len-idx)*sizeof(row_elt));
  110.     ************************************************************/
  111.       r->len++;
  112.       r->elt[idx].col = j;
  113.       return r->elt[idx].val = val;
  114.    }
  115.    /* else -- idx == -1, error in index/matrix! */
  116.    return 0.0;
  117. }
  118.  
  119. /* sp_mv_mlt -- sparse matrix/dense vector multiply
  120.    -- result is in out, which is returned unless out==NULL on entry
  121.    --  if out==NULL on entry then the result vector is created */
  122. VEC    *sp_mv_mlt(A,x,out)
  123. SPMAT    *A;
  124. VEC    *x, *out;
  125. {
  126.    int    i, j_idx, m, n, max_idx;
  127.    Real    sum, *x_ve;
  128.    SPROW    *r;
  129.    row_elt    *elts;
  130.    
  131.    if ( ! A || ! x )
  132.      error(E_NULL,"sp_mv_mlt");
  133.    if ( x->dim != A->n )
  134.      error(E_SIZES,"sp_mv_mlt");
  135.    if ( ! out || out->dim < A->m )
  136.      out = v_resize(out,A->m);
  137.    if ( out == x )
  138.      error(E_INSITU,"sp_mv_mlt");
  139.    m = A->m;    n = A->n;
  140.    x_ve = x->ve;
  141.    
  142.    for ( i = 0; i < m; i++ )
  143.    {
  144.       sum = 0.0;
  145.       r = &(A->row[i]);
  146.       max_idx = r->len;
  147.       elts    = r->elt;
  148.       for ( j_idx = 0; j_idx < max_idx; j_idx++, elts++ )
  149.     sum += elts->val*x_ve[elts->col];
  150.       out->ve[i] = sum;
  151.    }
  152.    return out;
  153. }
  154.  
  155. /* sp_vm_mlt -- sparse matrix/dense vector multiply from left
  156.    -- result is in out, which is returned unless out==NULL on entry
  157.    -- if out==NULL on entry then result vector is created & returned */
  158. VEC    *sp_vm_mlt(A,x,out)
  159. SPMAT    *A;
  160. VEC    *x, *out;
  161. {
  162.    int    i, j_idx, m, n, max_idx;
  163.    Real    tmp, *x_ve, *out_ve;
  164.    SPROW    *r;
  165.    row_elt    *elts;
  166.    
  167.    if ( ! A || ! x )
  168.      error(E_NULL,"sp_vm_mlt");
  169.    if ( x->dim != A->m )
  170.      error(E_SIZES,"sp_vm_mlt");
  171.    if ( ! out || out->dim < A->n )
  172.      out = v_resize(out,A->n);
  173.    if ( out == x )
  174.      error(E_INSITU,"sp_vm_mlt");
  175.    
  176.    m = A->m;    n = A->n;
  177.    v_zero(out);
  178.    x_ve = x->ve;    out_ve = out->ve;
  179.    
  180.    for ( i = 0; i < m; i++ )
  181.    {
  182.       r = A->row+i;
  183.       max_idx = r->len;
  184.       elts    = r->elt;
  185.       tmp = x_ve[i];
  186.       for ( j_idx = 0; j_idx < max_idx; j_idx++, elts++ )
  187.     out_ve[elts->col] += elts->val*tmp;
  188.    }
  189.    
  190.    return out;
  191. }
  192.  
  193.  
  194. /* sp_get -- get sparse matrix
  195.    -- len is number of elements available for each row without
  196.    allocating further memory */
  197. SPMAT    *sp_get(m,n,maxlen)
  198. int    m, n, maxlen;
  199. {
  200.    SPMAT    *A;
  201.    SPROW    *rows;
  202.    int    i;
  203.    
  204.    if ( m < 0 || n < 0 )
  205.      error(E_NEG,"sp_get");
  206.  
  207.    maxlen = max(maxlen,1);
  208.    
  209.    A = NEW(SPMAT);
  210.    if ( ! A )        /* can't allocate */
  211.      error(E_MEM,"sp_get");
  212.    else if (mem_info_is_on()) {
  213.       mem_bytes(TYPE_SPMAT,0,sizeof(SPMAT));
  214.       mem_numvar(TYPE_SPMAT,1);
  215.    }
  216.    /* fprintf(stderr,"Have SPMAT structure\n"); */
  217.    
  218.    A->row = rows = NEW_A(m,SPROW);
  219.    if ( ! A->row )        /* can't allocate */
  220.      error(E_MEM,"sp_get");
  221.    else if (mem_info_is_on()) {
  222.       mem_bytes(TYPE_SPMAT,0,m*sizeof(SPROW));
  223.    }
  224.    /* fprintf(stderr,"Have row structure array\n"); */
  225.    
  226.    A->start_row = NEW_A(n,int);
  227.    A->start_idx = NEW_A(n,int);
  228.    if ( ! A->start_row || ! A->start_idx )    /* can't allocate */
  229.      error(E_MEM,"sp_get");
  230.    else if (mem_info_is_on()) {
  231.       mem_bytes(TYPE_SPMAT,0,2*n*sizeof(int));
  232.    }
  233.    for ( i = 0; i < n; i++ )
  234.      A->start_row[i] = A->start_idx[i] = -1;
  235.    /* fprintf(stderr,"Have start_row array\n"); */
  236.    
  237.    A->m = A->max_m = m;
  238.    A->n = A->max_n = n;
  239.    
  240.    for ( i = 0; i < m; i++, rows++ )
  241.    {
  242.       rows->elt = NEW_A(maxlen,row_elt);
  243.       if ( ! rows->elt )
  244.     error(E_MEM,"sp_get");
  245.       else if (mem_info_is_on()) {
  246.      mem_bytes(TYPE_SPMAT,0,maxlen*sizeof(row_elt));
  247.       }
  248.       /* fprintf(stderr,"Have row %d element array\n",i); */
  249.       rows->len = 0;
  250.       rows->maxlen = maxlen;
  251.       rows->diag = -1;
  252.    }
  253.    
  254.    return A;
  255. }
  256.  
  257.  
  258. /* sp_free -- frees up the memory for a sparse matrix */
  259. int    sp_free(A)
  260. SPMAT    *A;
  261. {
  262.    SPROW    *r;
  263.    int    i;
  264.    
  265.    if ( ! A )
  266.      return -1;
  267.    if ( A->start_row != (int *)NULL ) {
  268.       if (mem_info_is_on()) {
  269.      mem_bytes(TYPE_SPMAT,A->max_n*sizeof(int),0);
  270.       }
  271.       free((char *)(A->start_row));
  272.    }
  273.    if ( A->start_idx != (int *)NULL ) {
  274.       if (mem_info_is_on()) {
  275.      mem_bytes(TYPE_SPMAT,A->max_n*sizeof(int),0);
  276.       }
  277.       
  278.       free((char *)(A->start_idx));
  279.    }
  280.    if ( ! A->row )
  281.    {
  282.       if (mem_info_is_on()) {
  283.      mem_bytes(TYPE_SPMAT,sizeof(SPMAT),0);
  284.      mem_numvar(TYPE_SPMAT,-1);
  285.       }
  286.       
  287.       free((char *)A);
  288.       return 0;
  289.    }
  290.    for ( i = 0; i < A->m; i++ )
  291.    {
  292.       r = &(A->row[i]);
  293.       if ( r->elt != (row_elt *)NULL ) {
  294.      if (mem_info_is_on()) {
  295.         mem_bytes(TYPE_SPMAT,A->row[i].maxlen*sizeof(row_elt),0);
  296.      }
  297.      free((char *)(r->elt));
  298.       }
  299.    }
  300.    
  301.    if (mem_info_is_on()) {
  302.       if (A->row) 
  303.     mem_bytes(TYPE_SPMAT,A->max_m*sizeof(SPROW),0);
  304.       mem_bytes(TYPE_SPMAT,sizeof(SPMAT),0);
  305.       mem_numvar(TYPE_SPMAT,-1);
  306.    }
  307.    
  308.    free((char *)(A->row));
  309.    free((char *)A);
  310.  
  311.    return 0;
  312. }
  313.  
  314.  
  315. /* sp_copy -- constructs a copy of a given matrix
  316.    -- note that the max_len fields (etc) are no larger in the copy
  317.    than necessary
  318.    -- result is returned */
  319. SPMAT    *sp_copy(A)
  320. SPMAT    *A;
  321. {
  322.    SPMAT    *out;
  323.    SPROW    *row1, *row2;
  324.    int    i;
  325.    
  326.    if ( A == SMNULL )
  327.      error(E_NULL,"sp_copy");
  328.    if ( ! (out=NEW(SPMAT)) )
  329.      error(E_MEM,"sp_copy");
  330.    else if (mem_info_is_on()) {
  331.       mem_bytes(TYPE_SPMAT,0,sizeof(SPMAT));
  332.       mem_numvar(TYPE_SPMAT,1);
  333.    }
  334.    out->m = out->max_m = A->m;    out->n = out->max_n = A->n;
  335.    
  336.    /* set up rows */
  337.    if ( ! (out->row=NEW_A(A->m,SPROW)) )
  338.      error(E_MEM,"sp_copy");
  339.    else if (mem_info_is_on()) {
  340.       mem_bytes(TYPE_SPMAT,0,A->m*sizeof(SPROW));
  341.    }
  342.    for ( i = 0; i < A->m; i++ )
  343.    {
  344.       row1 = &(A->row[i]);
  345.       row2 = &(out->row[i]);
  346.       if ( ! (row2->elt=NEW_A(max(row1->len,3),row_elt)) )
  347.     error(E_MEM,"sp_copy");
  348.       else if (mem_info_is_on()) {
  349.      mem_bytes(TYPE_SPMAT,0,max(row1->len,3)*sizeof(row_elt));
  350.       }
  351.       row2->len = row1->len;
  352.       row2->maxlen = max(row1->len,3);
  353.       row2->diag = row1->diag;
  354.       MEM_COPY((char *)(row1->elt),(char *)(row2->elt),
  355.            row1->len*sizeof(row_elt));
  356.    }
  357.    
  358.    /* set up start arrays -- for column access */
  359.    if ( ! (out->start_idx=NEW_A(A->n,int)) ||
  360.        ! (out->start_row=NEW_A(A->n,int)) )
  361.      error(E_MEM,"sp_copy");
  362.    else if (mem_info_is_on()) {
  363.       mem_bytes(TYPE_SPMAT,0,2*A->n*sizeof(int));
  364.    }
  365.    MEM_COPY((char *)(A->start_idx),(char *)(out->start_idx),
  366.         A->n*sizeof(int));
  367.    MEM_COPY((char *)(A->start_row),(char *)(out->start_row),
  368.         A->n*sizeof(int));
  369.    
  370.    return out;
  371. }
  372.  
  373. /* sp_col_access -- set column access path; i.e. nxt_row, nxt_idx fields
  374.    -- returns A */
  375. SPMAT    *sp_col_access(A)
  376. SPMAT    *A;
  377. {
  378.    int    i, j, j_idx, len, m, n;
  379.    SPROW    *row;
  380.    row_elt    *r_elt;
  381.    int    *start_row, *start_idx;
  382.    
  383.    if ( A == SMNULL )
  384.      error(E_NULL,"sp_col_access");
  385.    
  386.    m = A->m;    n = A->n;
  387.    
  388.    /* initialise start_row and start_idx */
  389.    start_row = A->start_row;    start_idx = A->start_idx;
  390.    for ( j = 0; j < n; j++ )
  391.    {    *start_row++ = -1;    *start_idx++ = -1;    }
  392.    
  393.    start_row = A->start_row;    start_idx = A->start_idx;
  394.    
  395.    /* now work UP the rows, setting nxt_row, nxt_idx fields */
  396.    for ( i = m-1; i >= 0; i-- )
  397.    {
  398.       row = &(A->row[i]);
  399.       r_elt = row->elt;
  400.       len   = row->len;
  401.       for ( j_idx = 0; j_idx < len; j_idx++, r_elt++ )
  402.       {
  403.      j = r_elt->col;
  404.      r_elt->nxt_row = start_row[j];
  405.      r_elt->nxt_idx = start_idx[j];
  406.      start_row[j] = i;
  407.      start_idx[j] = j_idx;
  408.       }
  409.    }
  410.    
  411.    A->flag_col = TRUE;
  412.    return A;
  413. }
  414.  
  415. /* sp_diag_access -- set diagonal access path(s) */
  416. SPMAT    *sp_diag_access(A)
  417. SPMAT    *A;
  418. {
  419.    int    i, m;
  420.    SPROW    *row;
  421.    
  422.    if ( A == SMNULL )
  423.      error(E_NULL,"sp_diag_access");
  424.    
  425.    m = A->m;
  426.    
  427.    row = A->row;
  428.    for ( i = 0; i < m; i++, row++ )
  429.      row->diag = sprow_idx(row,i);
  430.    
  431.    A->flag_diag = TRUE;
  432.    
  433.    return A;
  434. }
  435.  
  436. /* sp_m2dense -- convert a sparse matrix to a dense one */
  437. MAT    *sp_m2dense(A,out)
  438. SPMAT    *A;
  439. MAT    *out;
  440. {
  441.    int    i, j_idx;
  442.    SPROW    *row;
  443.    row_elt    *elt;
  444.    
  445.    if ( ! A )
  446.      error(E_NULL,"sp_m2dense");
  447.    if ( ! out || out->m < A->m || out->n < A->n )
  448.      out = m_get(A->m,A->n);
  449.    
  450.    m_zero(out);
  451.    for ( i = 0; i < A->m; i++ )
  452.    {
  453.       row = &(A->row[i]);
  454.       elt = row->elt;
  455.       for ( j_idx = 0; j_idx < row->len; j_idx++, elt++ )
  456.     out->me[i][elt->col] = elt->val;
  457.    }
  458.    
  459.    return out;
  460. }
  461.  
  462.  
  463. /*  C = A+B, can be in situ */
  464. SPMAT *sp_add(A,B,C)
  465. SPMAT *A, *B, *C;
  466. {
  467.    int i, in_situ;
  468.    SPROW *rc;
  469.    static SPROW *tmp;
  470.  
  471.    if ( ! A || ! B )
  472.      error(E_NULL,"sp_add");
  473.    if ( A->m != B->m || A->n != B->n )
  474.      error(E_SIZES,"sp_add");
  475.    if (C == A || C == B)
  476.      in_situ = TRUE;
  477.    else in_situ = FALSE;
  478.  
  479.    if ( ! C )
  480.      C = sp_get(A->m,A->n,5);
  481.    else {
  482.       if ( C->m != A->m || C->n != A->n  )
  483.     error(E_SIZES,"sp_add");
  484.       if (!in_situ) sp_zero(C);
  485.    }
  486.  
  487.    if (tmp == (SPROW *)NULL && in_situ) {
  488.       tmp = sprow_get(MINROWLEN);
  489.       MEM_STAT_REG(tmp,TYPE_SPROW);
  490.    }
  491.  
  492.    if (in_situ)
  493.      for (i=0; i < A->m; i++) {
  494.     rc = &(C->row[i]);
  495.     sprow_add(&(A->row[i]),&(B->row[i]),0,tmp,TYPE_SPROW);
  496.     sprow_resize(rc,tmp->len,TYPE_SPMAT);
  497.     MEM_COPY(tmp->elt,rc->elt,tmp->len*sizeof(row_elt));
  498.     rc->len = tmp->len;
  499.      }
  500.    else
  501.      for (i=0; i < A->m; i++) {
  502.     sprow_add(&(A->row[i]),&(B->row[i]),0,&(C->row[i]),TYPE_SPMAT);
  503.      }
  504.  
  505.    C->flag_col = C->flag_diag = FALSE;
  506.  
  507.    return C;
  508. }
  509.  
  510. /*  C = A-B, cannot be in situ */
  511. SPMAT *sp_sub(A,B,C)
  512. SPMAT *A, *B, *C;
  513. {
  514.    int i, in_situ;
  515.    SPROW *rc;
  516.    static SPROW *tmp;
  517.    
  518.    if ( ! A || ! B )
  519.      error(E_NULL,"sp_sub");
  520.    if ( A->m != B->m || A->n != B->n )
  521.      error(E_SIZES,"sp_sub");
  522.    if (C == A || C == B)
  523.      in_situ = TRUE;
  524.    else in_situ = FALSE;
  525.  
  526.    if ( ! C )
  527.      C = sp_get(A->m,A->n,5);
  528.    else {
  529.       if ( C->m != A->m || C->n != A->n  )
  530.     error(E_SIZES,"sp_sub");
  531.       if (!in_situ) sp_zero(C);
  532.    }
  533.  
  534.    if (tmp == (SPROW *)NULL && in_situ) {
  535.       tmp = sprow_get(MINROWLEN);
  536.       MEM_STAT_REG(tmp,TYPE_SPROW);
  537.    }
  538.  
  539.    if (in_situ)
  540.      for (i=0; i < A->m; i++) {
  541.     rc = &(C->row[i]);
  542.     sprow_sub(&(A->row[i]),&(B->row[i]),0,tmp,TYPE_SPROW);
  543.     sprow_resize(rc,tmp->len,TYPE_SPMAT);
  544.     MEM_COPY(tmp->elt,rc->elt,tmp->len*sizeof(row_elt));
  545.     rc->len = tmp->len;
  546.      }
  547.    else
  548.      for (i=0; i < A->m; i++) {
  549.     sprow_sub(&(A->row[i]),&(B->row[i]),0,&(C->row[i]),TYPE_SPMAT);
  550.      }
  551.  
  552.    C->flag_col = C->flag_diag = FALSE;
  553.    
  554.    return C;
  555. }
  556.  
  557. /*  C = A+alpha*B, cannot be in situ */
  558. SPMAT *sp_mltadd(A,B,alpha,C)
  559. SPMAT *A, *B, *C;
  560. double alpha;
  561. {
  562.    int i, in_situ;
  563.    SPROW *rc;
  564.    static SPROW *tmp;
  565.  
  566.    if ( ! A || ! B )
  567.      error(E_NULL,"sp_mltadd");
  568.    if ( A->m != B->m || A->n != B->n )
  569.      error(E_SIZES,"sp_mltadd");
  570.    if (C == A || C == B)
  571.      in_situ = TRUE;
  572.    else in_situ = FALSE;
  573.  
  574.    if ( ! C )
  575.      C = sp_get(A->m,A->n,5);
  576.    else {
  577.       if ( C->m != A->m || C->n != A->n  )
  578.     error(E_SIZES,"sp_mltadd");
  579.       if (!in_situ) sp_zero(C);
  580.    }
  581.  
  582.    if (tmp == (SPROW *)NULL && in_situ) {
  583.       tmp = sprow_get(MINROWLEN);
  584.       MEM_STAT_REG(tmp,TYPE_SPROW);
  585.    }
  586.  
  587.    if (in_situ)
  588.      for (i=0; i < A->m; i++) {
  589.     rc = &(C->row[i]);
  590.     sprow_mltadd(&(A->row[i]),&(B->row[i]),alpha,0,tmp,TYPE_SPROW);
  591.     sprow_resize(rc,tmp->len,TYPE_SPMAT);
  592.     MEM_COPY(tmp->elt,rc->elt,tmp->len*sizeof(row_elt));
  593.     rc->len = tmp->len;
  594.      }
  595.    else
  596.      for (i=0; i < A->m; i++) {
  597.     sprow_mltadd(&(A->row[i]),&(B->row[i]),alpha,0,
  598.              &(C->row[i]),TYPE_SPMAT);
  599.      }
  600.    
  601.    C->flag_col = C->flag_diag = FALSE;
  602.    
  603.    return C;
  604. }
  605.  
  606.  
  607.  
  608. /*  B = alpha*A, can be in situ */
  609. SPMAT *sp_smlt(A,alpha,B)
  610. SPMAT *A, *B;
  611. double alpha;
  612. {
  613.    int i;
  614.  
  615.    if ( ! A )
  616.      error(E_NULL,"sp_smlt");
  617.    if ( ! B )
  618.      B = sp_get(A->m,A->n,5);
  619.    else
  620.      if ( A->m != B->m || A->n != B->n )
  621.        error(E_SIZES,"sp_smlt");
  622.  
  623.    for (i=0; i < A->m; i++) {
  624.       sprow_smlt(&(A->row[i]),alpha,0,&(B->row[i]),TYPE_SPMAT);
  625.    }
  626.    return B;
  627. }
  628.  
  629.  
  630.  
  631. /* sp_zero -- zero all the (represented) elements of a sparse matrix */
  632. SPMAT    *sp_zero(A)
  633. SPMAT    *A;
  634. {
  635.    int    i, idx, len;
  636.    row_elt    *elt;
  637.    
  638.    if ( ! A )
  639.      error(E_NULL,"sp_zero");
  640.    
  641.    for ( i = 0; i < A->m; i++ )
  642.    {
  643.       elt = A->row[i].elt;
  644.       len = A->row[i].len;
  645.       for ( idx = 0; idx < len; idx++ )
  646.     (*elt++).val = 0.0;
  647.    }
  648.    
  649.    return A;
  650. }
  651.  
  652. /* sp_copy2 -- copy sparse matrix (type 2) 
  653.    -- keeps structure of the OUT matrix */
  654. SPMAT    *sp_copy2(A,OUT)
  655. SPMAT    *A, *OUT;
  656. {
  657.    int    i /* , idx, len1, len2 */;
  658.    SPROW    *r1, *r2;
  659.    static SPROW    *scratch = (SPROW *)NULL;
  660.    /* row_elt    *e1, *e2; */
  661.    void        sprow_foutput();
  662.    
  663.    if ( ! A )
  664.      error(E_NULL,"sp_copy2");
  665.    if ( ! OUT )
  666.      OUT = sp_get(A->m,A->n,10);
  667.    if ( ! scratch ) {
  668.       scratch = sprow_xpd(scratch,MINROWLEN,TYPE_SPROW);
  669.       MEM_STAT_REG(scratch,TYPE_SPROW);
  670.    }
  671.  
  672.    if ( OUT->m < A->m )
  673.    {
  674.       if (mem_info_is_on()) {
  675.      mem_bytes(TYPE_SPMAT,A->max_m*sizeof(SPROW),
  676.               A->m*sizeof(SPROW));
  677.       }
  678.  
  679.       OUT->row = RENEW(OUT->row,A->m,SPROW);
  680.       if ( ! OUT->row )
  681.     error(E_MEM,"sp_copy2");
  682.       
  683.       for ( i = OUT->m; i < A->m; i++ )
  684.       {
  685.      OUT->row[i].elt = NEW_A(MINROWLEN,row_elt);
  686.      if ( ! OUT->row[i].elt )
  687.        error(E_MEM,"sp_copy2");
  688.      else if (mem_info_is_on()) {
  689.         mem_bytes(TYPE_SPMAT,0,MINROWLEN*sizeof(row_elt));
  690.      }
  691.      
  692.      OUT->row[i].maxlen = MINROWLEN;
  693.      OUT->row[i].len = 0;
  694.       }
  695.       OUT->m = A->m;
  696.    }
  697.    
  698.    OUT->flag_col = OUT->flag_diag = FALSE;
  699.    /* sp_zero(OUT); */
  700.  
  701.    for ( i = 0; i < A->m; i++ )
  702.    {
  703.       r1 = &(A->row[i]);    r2 = &(OUT->row[i]);
  704.       sprow_copy(r1,r2,scratch,TYPE_SPROW);
  705.       if ( r2->maxlen < scratch->len )
  706.     sprow_xpd(r2,scratch->len,TYPE_SPMAT);
  707.       MEM_COPY((char *)(scratch->elt),(char *)(r2->elt),
  708.            scratch->len*sizeof(row_elt));
  709.       r2->len = scratch->len;
  710.       /*******************************************************
  711.     e1 = r1->elt;        e2 = r2->elt;
  712.     len1 = r1->len;        len2 = r2->len;
  713.     for ( idx = 0; idx < len2; idx++, e2++ )
  714.     e2->val = 0.0;
  715.     for ( idx = 0; idx < len1; idx++, e1++ )
  716.     sprow_set_val(r2,e1->col,e1->val);
  717.     *******************************************************/
  718.    }
  719.  
  720.    sp_col_access(OUT);
  721.    return OUT;
  722. }
  723.  
  724. /* sp_resize -- resize a sparse matrix
  725.    -- don't destroying any contents if possible
  726.    -- returns resized matrix */
  727. SPMAT    *sp_resize(A,m,n)
  728. SPMAT    *A;
  729. int    m, n;
  730. {
  731.    int    i, len;
  732.    SPROW    *r;
  733.    
  734.    if (m < 0 || n < 0)
  735.      error(E_NEG,"sp_resize");
  736.  
  737.    if ( ! A )
  738.      return sp_get(m,n,10);
  739.  
  740.    if (m == A->m && n == A->n)
  741.      return A;
  742.  
  743.    if ( m <= A->max_m )
  744.    {
  745.       for ( i = A->m; i < m; i++ )
  746.     A->row[i].len = 0;
  747.       A->m = m;
  748.    }
  749.    else
  750.    {
  751.       if (mem_info_is_on()) {
  752.      mem_bytes(TYPE_SPMAT,A->max_m*sizeof(SPROW),
  753.              m*sizeof(SPROW));
  754.       }
  755.  
  756.       A->row = RENEW(A->row,(unsigned)m,SPROW);
  757.       if ( ! A->row )
  758.     error(E_MEM,"sp_resize");
  759.       for ( i = A->m; i < m; i++ )
  760.       {
  761.      if ( ! (A->row[i].elt = NEW_A(MINROWLEN,row_elt)) )
  762.        error(E_MEM,"sp_resize");
  763.      else if (mem_info_is_on()) {
  764.         mem_bytes(TYPE_SPMAT,0,MINROWLEN*sizeof(row_elt));
  765.      }
  766.      A->row[i].len = 0;    A->row[i].maxlen = MINROWLEN;
  767.       }
  768.       A->m = A->max_m = m;
  769.    }
  770.    
  771.    if ( n <= A->n )
  772.    {    /* only have to update the start_idx & start_row arrays */
  773.       A->n = n;
  774.       if (mem_info_is_on()) {
  775.      mem_bytes(TYPE_SPMAT,2*A->max_n*sizeof(int),
  776.               2*n*sizeof(int));
  777.       }
  778.  
  779.       A->start_row = RENEW(A->start_row,(unsigned)n,int);
  780.       A->start_idx = RENEW(A->start_idx,(unsigned)n,int);
  781.       if ( ! A->start_row || ! A->start_idx )
  782.     error(E_MEM,"sp_resize");
  783.  
  784.       return A;
  785.    }
  786.    
  787.    for ( i = 0; i < A->m; i++ )
  788.    {
  789.       r = &(A->row[i]);
  790.       len = sprow_idx(r,n);
  791.       if ( len < 0 )
  792.     len = -(len+2);
  793.       if ( len < 0 )
  794.     error(E_MEM,"sp_resize");
  795.       r->len = len;
  796.    }
  797.    
  798.    return A;
  799. }
  800.  
  801.  
  802. /* sp_compact -- removes zeros and near-zeros from a sparse matrix */
  803. SPMAT    *sp_compact(A,tol)
  804. SPMAT    *A;
  805. double    tol;
  806. {
  807.    int    i, idx1, idx2;
  808.    SPROW    *r;
  809.    row_elt    *elt1, *elt2;
  810.    
  811.    if (  ! A )
  812.      error(E_NULL,"sp_compact");
  813.    if ( tol < 0.0 )
  814.      error(E_RANGE,"sp_compact");
  815.    
  816.    A->flag_col = A->flag_diag = FALSE;
  817.    
  818.    for ( i = 0; i < A->m; i++ )
  819.    {
  820.       r = &(A->row[i]);
  821.       elt1 = elt2 = r->elt;
  822.       idx1 = idx2 = 0;
  823.       while ( idx1 < r->len )
  824.       {
  825.      /* printf("# sp_compact: idx1 = %d, idx2 = %d\n",idx1,idx2); */
  826.      if ( fabs(elt1->val) <= tol )
  827.      {    idx1++;    elt1++;    continue;    }
  828.      if ( elt1 != elt2 )
  829.        MEM_COPY(elt1,elt2,sizeof(row_elt));
  830.      idx1++;    elt1++;
  831.      idx2++;    elt2++;
  832.       }
  833.       r->len = idx2;
  834.    }
  835.    
  836.    return A;
  837. }
  838.  
  839. /* varying number of arguments */
  840.  
  841. #ifdef ANSI_C
  842.  
  843. /* To allocate memory to many arguments. 
  844.    The function should be called:
  845.    sp_get_vars(m,n,deg,&x,&y,&z,...,NULL);
  846.    where 
  847.      int m,n,deg;
  848.      SPMAT *x, *y, *z,...;
  849.      The last argument should be NULL ! 
  850.      m x n is the dimension of matrices x,y,z,...
  851.      returned value is equal to the number of allocated variables
  852. */
  853.  
  854. int sp_get_vars(int m,int n,int deg,...) 
  855. {
  856.    va_list ap;
  857.    int i=0;
  858.    SPMAT **par;
  859.    
  860.    va_start(ap, deg);
  861.    while (par = va_arg(ap,SPMAT **)) {   /* NULL ends the list*/
  862.       *par = sp_get(m,n,deg);
  863.       i++;
  864.    } 
  865.  
  866.    va_end(ap);
  867.    return i;
  868. }
  869.  
  870.  
  871. /* To resize memory for many arguments. 
  872.    The function should be called:
  873.    sp_resize_vars(m,n,&x,&y,&z,...,NULL);
  874.    where 
  875.      int m,n;
  876.      SPMAT *x, *y, *z,...;
  877.      The last argument should be NULL ! 
  878.      m X n is the resized dimension of matrices x,y,z,...
  879.      returned value is equal to the number of allocated variables.
  880.      If one of x,y,z,.. arguments is NULL then memory is allocated to this 
  881.      argument. 
  882. */
  883.   
  884. int sp_resize_vars(int m,int n,...) 
  885. {
  886.    va_list ap;
  887.    int i=0;
  888.    SPMAT **par;
  889.    
  890.    va_start(ap, n);
  891.    while (par = va_arg(ap,SPMAT **)) {   /* NULL ends the list*/
  892.       *par = sp_resize(*par,m,n);
  893.       i++;
  894.    } 
  895.  
  896.    va_end(ap);
  897.    return i;
  898. }
  899.  
  900. /* To deallocate memory for many arguments. 
  901.    The function should be called:
  902.    sp_free_vars(&x,&y,&z,...,NULL);
  903.    where 
  904.      SPMAT *x, *y, *z,...;
  905.      The last argument should be NULL ! 
  906.      There must be at least one not NULL argument.
  907.      returned value is equal to the number of allocated variables.
  908.      Returned value of x,y,z,.. is VNULL.
  909. */
  910.  
  911. int sp_free_vars(SPMAT **va,...)
  912. {
  913.    va_list ap;
  914.    int i=1;
  915.    SPMAT **par;
  916.    
  917.    sp_free(*va);
  918.    *va = (SPMAT *) NULL;
  919.    va_start(ap, va);
  920.    while (par = va_arg(ap,SPMAT **)) {   /* NULL ends the list*/
  921.       sp_free(*par); 
  922.       *par = (SPMAT *)NULL;
  923.       i++;
  924.    } 
  925.  
  926.    va_end(ap);
  927.    return i;
  928. }
  929.  
  930.  
  931. #elif VARARGS
  932.  
  933. /* To allocate memory to many arguments. 
  934.    The function should be called:
  935.    sp_get_vars(m,n,deg,&x,&y,&z,...,NULL);
  936.    where 
  937.      int m,n,deg;
  938.      SPMAT *x, *y, *z,...;
  939.      The last argument should be NULL ! 
  940.      m x n is the dimension of matrices x,y,z,...
  941.      returned value is equal to the number of allocated variables
  942. */
  943.  
  944. int sp_get_vars(va_alist) va_dcl
  945. {
  946.    va_list ap;
  947.    int i=0, m, n, deg;
  948.    SPMAT **par;
  949.    
  950.    va_start(ap);
  951.    m = va_arg(ap,int);
  952.    n = va_arg(ap,int);
  953.    deg = va_arg(ap,int);
  954.    while (par = va_arg(ap,SPMAT **)) {   /* NULL ends the list*/
  955.       *par = sp_get(m,n,deg);
  956.       i++;
  957.    } 
  958.  
  959.    va_end(ap);
  960.    return i;
  961. }
  962.  
  963.  
  964. /* To resize memory for many arguments. 
  965.    The function should be called:
  966.    sp_resize_vars(m,n,&x,&y,&z,...,NULL);
  967.    where 
  968.      int m,n;
  969.      SPMAT *x, *y, *z,...;
  970.      The last argument should be NULL ! 
  971.      m X n is the resized dimension of matrices x,y,z,...
  972.      returned value is equal to the number of allocated variables.
  973.      If one of x,y,z,.. arguments is NULL then memory is allocated to this 
  974.      argument. 
  975. */
  976.  
  977. int sp_resize_vars(va_alist) va_dcl
  978. {
  979.    va_list ap;
  980.    int i=0, m, n;
  981.    SPMAT **par;
  982.    
  983.    va_start(ap);
  984.    m = va_arg(ap,int);
  985.    n = va_arg(ap,int);
  986.    while (par = va_arg(ap,SPMAT **)) {   /* NULL ends the list*/
  987.       *par = sp_resize(*par,m,n);
  988.       i++;
  989.    } 
  990.  
  991.    va_end(ap);
  992.    return i;
  993. }
  994.  
  995.  
  996.  
  997. /* To deallocate memory for many arguments. 
  998.    The function should be called:
  999.    sp_free_vars(&x,&y,&z,...,NULL);
  1000.    where 
  1001.      SPMAT *x, *y, *z,...;
  1002.      The last argument should be NULL ! 
  1003.      There must be at least one not NULL argument.
  1004.      returned value is equal to the number of allocated variables.
  1005.      Returned value of x,y,z,.. is VNULL.
  1006. */
  1007.  
  1008. int sp_free_vars(va_alist) va_dcl
  1009. {
  1010.    va_list ap;
  1011.    int i=0;
  1012.    SPMAT **par;
  1013.    
  1014.    va_start(ap);
  1015.    while (par = va_arg(ap,SPMAT **)) {   /* NULL ends the list*/
  1016.       sp_free(*par); 
  1017.       *par = (SPMAT *)NULL;
  1018.       i++;
  1019.    } 
  1020.  
  1021.    va_end(ap);
  1022.    return i;
  1023. }
  1024.  
  1025.  
  1026.  
  1027. #endif
  1028.  
  1029.