1 /* ========================================================================== */
2 /* === UMF_tuple_lengths ==================================================== */
3 /* ========================================================================== */
4
5 /* -------------------------------------------------------------------------- */
6 /* Copyright (c) 2005-2012 by Timothy A. Davis, http://www.suitesparse.com. */
7 /* All Rights Reserved. See ../Doc/License.txt for License. */
8 /* -------------------------------------------------------------------------- */
9
10 /* Determine the tuple list lengths, and the amount of memory required for */
11 /* them. Return the amount of memory needed to store all the tuples. */
12 /* This routine assumes that the tuple lists themselves are either already */
13 /* deallocated, or will be shortly (so Row[ ].tlen and Col[ ].tlen are */
14 /* overwritten) */
15
16 #include "umf_internal.h"
17 #include "umf_tuple_lengths.h"
18
UMF_tuple_lengths(NumericType * Numeric,WorkType * Work,double * p_dusage)19 GLOBAL Int UMF_tuple_lengths /* return memory usage */
20 (
21 NumericType *Numeric,
22 WorkType *Work,
23 double *p_dusage /* output argument */
24 )
25 {
26 /* ---------------------------------------------------------------------- */
27 /* local variables */
28 /* ---------------------------------------------------------------------- */
29
30 double dusage ;
31 Int e, nrows, ncols, nel, i, *Rows, *Cols, row, col, n_row, n_col, *E,
32 *Row_degree, *Row_tlen, *Col_degree, *Col_tlen, usage, n1 ;
33 Element *ep ;
34 Unit *p ;
35
36 /* ---------------------------------------------------------------------- */
37 /* get parameters */
38 /* ---------------------------------------------------------------------- */
39
40 E = Work->E ;
41 Row_degree = Numeric->Rperm ; /* for NON_PIVOTAL_ROW macro only */
42 Col_degree = Numeric->Cperm ; /* for NON_PIVOTAL_COL macro only */
43 Row_tlen = Numeric->Uilen ;
44 Col_tlen = Numeric->Lilen ;
45 n_row = Work->n_row ;
46 n_col = Work->n_col ;
47 n1 = Work->n1 ;
48 nel = Work->nel ;
49
50 DEBUG3 (("TUPLE_LENGTHS: n_row "ID" n_col "ID" nel "ID"\n",
51 n_row, n_col, nel)) ;
52 ASSERT (nel < Work->elen) ;
53
54 /* tuple list lengths already initialized to zero */
55
56 /* ---------------------------------------------------------------------- */
57 /* scan each element: count tuple list lengths (include element 0) */
58 /* ---------------------------------------------------------------------- */
59
60 for (e = 1 ; e <= nel ; e++) /* for all elements, in any order */
61 {
62 if (E [e])
63 {
64 #ifndef NDEBUG
65 UMF_dump_element (Numeric, Work, e, FALSE) ;
66 #endif
67 p = Numeric->Memory + E [e] ;
68 GET_ELEMENT_PATTERN (ep, p, Cols, Rows, ncols) ;
69 nrows = ep->nrows ;
70 for (i = 0 ; i < nrows ; i++)
71 {
72 row = Rows [i] ;
73 ASSERT (row == EMPTY || (row >= n1 && row < n_row)) ;
74 if (row >= n1)
75 {
76 ASSERT (NON_PIVOTAL_ROW (row)) ;
77 Row_tlen [row] ++ ;
78 }
79 }
80 for (i = 0 ; i < ncols ; i++)
81 {
82 col = Cols [i] ;
83 ASSERT (col == EMPTY || (col >= n1 && col < n_col)) ;
84 if (col >= n1)
85 {
86 ASSERT (NON_PIVOTAL_COL (col)) ;
87 Col_tlen [col] ++ ;
88 }
89 }
90 }
91 }
92
93 /* note: tuple lengths are now modified, but the tuple lists are not */
94 /* updated to reflect that fact. */
95
96 /* ---------------------------------------------------------------------- */
97 /* determine the required memory to hold all the tuple lists */
98 /* ---------------------------------------------------------------------- */
99
100 DEBUG0 (("UMF_build_tuples_usage\n")) ;
101
102 usage = 0 ;
103 dusage = 0 ;
104
105 ASSERT (Col_tlen && Col_degree) ;
106
107 for (col = n1 ; col < n_col ; col++)
108 {
109 if (NON_PIVOTAL_COL (col))
110 {
111 usage += 1 + UNITS (Tuple, TUPLES (Col_tlen [col])) ;
112 dusage += 1 + DUNITS (Tuple, TUPLES (Col_tlen [col])) ;
113 DEBUG0 ((" col: "ID" tlen "ID" usage so far: "ID"\n",
114 col, Col_tlen [col], usage)) ;
115 }
116 }
117
118 ASSERT (Row_tlen && Row_degree) ;
119
120 for (row = n1 ; row < n_row ; row++)
121 {
122 if (NON_PIVOTAL_ROW (row))
123 {
124 usage += 1 + UNITS (Tuple, TUPLES (Row_tlen [row])) ;
125 dusage += 1 + DUNITS (Tuple, TUPLES (Row_tlen [row])) ;
126 DEBUG0 ((" row: "ID" tlen "ID" usage so far: "ID"\n",
127 row, Row_tlen [row], usage)) ;
128 }
129 }
130
131 DEBUG0 (("UMF_build_tuples_usage "ID" %g\n", usage, dusage)) ;
132
133 *p_dusage = dusage ;
134 return (usage) ;
135 }
136