1 /* ========================================================================== */
2 /* === UMF_fsize ============================================================ */
3 /* ========================================================================== */
4
5 /* -------------------------------------------------------------------------- */
6 /* Copyright (c) 2005-2012 by Timothy A. Davis, http://www.suitesparse.com. */
7 /* All Rights Reserved. See ../Doc/License.txt.txt for License. */
8 /* -------------------------------------------------------------------------- */
9
10 /* Determine the largest frontal matrix size for each subtree. Called by
11 * UMF_colamd and UMF_analyze. Only required to sort the children of each
12 * node prior to AMD_postorder. */
13
14 #include "umf_internal.h"
15 #include "umf_fsize.h"
16
UMF_fsize(Int nn,Int Fsize[],Int Fnrows[],Int Fncols[],Int Parent[],Int Npiv[])17 GLOBAL void UMF_fsize
18 (
19 Int nn,
20 Int Fsize [ ],
21 Int Fnrows [ ],
22 Int Fncols [ ],
23 Int Parent [ ],
24 Int Npiv [ ]
25 )
26 {
27 Int j, parent, frsize, r, c ;
28
29 for (j = 0 ; j < nn ; j++)
30 {
31 Fsize [j] = EMPTY ;
32 }
33
34 /* ---------------------------------------------------------------------- */
35 /* find max front size for tree rooted at node j, for each front j */
36 /* ---------------------------------------------------------------------- */
37
38 DEBUG1 (("\n\n========================================FRONTS:\n")) ;
39 for (j = 0 ; j < nn ; j++)
40 {
41 if (Npiv [j] > 0)
42 {
43 /* this is a frontal matrix */
44 parent = Parent [j] ;
45 r = Fnrows [j] ;
46 c = Fncols [j] ;
47 frsize = r * c ;
48 /* avoid integer overflow */
49 if (INT_OVERFLOW (((double) r) * ((double) c)))
50 {
51 /* :: frsize int overflow :: */
52 frsize = Int_MAX ;
53 }
54 DEBUG1 ((""ID" : npiv "ID" size "ID" parent "ID" ",
55 j, Npiv [j], frsize, parent)) ;
56 Fsize [j] = MAX (Fsize [j], frsize) ;
57 DEBUG1 (("Fsize [j = "ID"] = "ID"\n", j, Fsize [j])) ;
58 if (parent != EMPTY)
59 {
60 /* find the maximum frontsize of self and children */
61 ASSERT (Npiv [parent] > 0) ;
62 ASSERT (parent > j) ;
63 Fsize [parent] = MAX (Fsize [parent], Fsize [j]) ;
64 DEBUG1 (("Fsize [parent = "ID"] = "ID"\n",
65 parent, Fsize [parent]));
66 }
67 }
68 }
69 }
70