[petsc-users] coloring algorithms

[Barry Smith]

  Please send the matrix as a binary file.

   Are you computing a distance one coloring or distance 2. 2 is needed for Jacobians.


> On Mar 23, 2017, at 4:57 PM, Kong, Fande <fande.kong at inl.gov> wrote:
> 
> Thanks, Hong,
> 
> I did some tests with a matrix (40x40):
> 
> row 0: (0, 1.)  (2, 1.)  (3, 1.)  (11, 1.)  (14, 1.)  (15, 1.)  (19, 1.)  (22, 1.)  (23, 1.)  (24, 1.)  (27, 1.)  (28, 1.) 
> row 1: (1, 1.)  (2, 1.)  (3, 1.)  (6, 1.)  (16, 1.)  (17, 1.)  (18, 1.)  (21, 1.)  (33, 1.) 
> row 2: (0, 1.)  (1, 1.)  (2, 1.)  (3, 1.)  (6, 1.)  (7, 1.)  (9, 1.)  (10, 1.)  (16, 1.)  (19, 1.)  (20, 1.) 
> row 3: (0, 1.)  (1, 1.)  (2, 1.)  (3, 1.)  (5, 1.)  (11, 1.)  (18, 1.)  (19, 1.)  (21, 1.)  (22, 1.)  (31, 1.)  (33, 1.) 
> row 4: (4, 1.)  (14, 1.)  (15, 1.)  (19, 1.)  (24, 1.)  (25, 1.)  (28, 1.)  (30, 1.)  (37, 1.)  (38, 1.) 
> row 5: (3, 1.)  (5, 1.)  (11, 1.)  (17, 1.)  (22, 1.)  (26, 1.)  (31, 1.)  (32, 1.)  (33, 1.)  (34, 1.) 
> row 6: (1, 1.)  (2, 1.)  (6, 1.)  (7, 1.)  (9, 1.)  (10, 1.)  (16, 1.)  (20, 1.)  (25, 1.)  (30, 1.) 
> row 7: (2, 1.)  (6, 1.)  (7, 1.)  (9, 1.)  (10, 1.)  (13, 1.)  (17, 1.)  (20, 1.)  (32, 1.)  (34, 1.) 
> row 8: (8, 1.)  (9, 1.)  (12, 1.)  (13, 1.)  (26, 1.)  (29, 1.)  (30, 1.)  (36, 1.)  (38, 1.)  (39, 1.) 
> row 9: (2, 1.)  (6, 1.)  (7, 1.)  (8, 1.)  (9, 1.)  (10, 1.)  (13, 1.)  (16, 1.)  (17, 1.)  (20, 1.)  (25, 1.)  (30, 1.)  (34, 1.) 
> row 10: (2, 1.)  (6, 1.)  (7, 1.)  (9, 1.)  (10, 1.)  (19, 1.)  (20, 1.)  (29, 1.)  (32, 1.)  (34, 1.) 
> row 11: (0, 1.)  (3, 1.)  (5, 1.)  (11, 1.)  (12, 1.)  (14, 1.)  (15, 1.)  (19, 1.)  (22, 1.)  (23, 1.)  (26, 1.)  (27, 1.)  (31, 1.) 
> row 12: (8, 1.)  (11, 1.)  (12, 1.)  (13, 1.)  (15, 1.)  (22, 1.)  (23, 1.)  (26, 1.)  (27, 1.)  (35, 1.)  (36, 1.)  (39, 1.) 
> row 13: (7, 1.)  (8, 1.)  (9, 1.)  (12, 1.)  (13, 1.)  (17, 1.)  (23, 1.)  (26, 1.)  (30, 1.)  (34, 1.)  (35, 1.)  (36, 1.) 
> row 14: (0, 1.)  (4, 1.)  (11, 1.)  (14, 1.)  (15, 1.)  (19, 1.)  (21, 1.)  (23, 1.)  (24, 1.)  (25, 1.)  (28, 1.)  (38, 1.) 
> row 15: (0, 1.)  (4, 1.)  (11, 1.)  (12, 1.)  (14, 1.)  (15, 1.)  (18, 1.)  (21, 1.)  (23, 1.)  (25, 1.)  (27, 1.)  (28, 1.)  (35, 1.)  (36, 1.) 
> row 16: (1, 1.)  (2, 1.)  (6, 1.)  (9, 1.)  (16, 1.)  (18, 1.)  (21, 1.)  (25, 1.)  (30, 1.) 
> row 17: (1, 1.)  (5, 1.)  (7, 1.)  (9, 1.)  (13, 1.)  (17, 1.)  (18, 1.)  (21, 1.)  (31, 1.)  (33, 1.)  (34, 1.)  (35, 1.)  (36, 1.) 
> row 18: (1, 1.)  (3, 1.)  (15, 1.)  (16, 1.)  (17, 1.)  (18, 1.)  (21, 1.)  (23, 1.)  (31, 1.)  (33, 1.)  (35, 1.)  (36, 1.) 
> row 19: (0, 1.)  (2, 1.)  (3, 1.)  (4, 1.)  (10, 1.)  (11, 1.)  (14, 1.)  (19, 1.)  (20, 1.)  (24, 1.)  (29, 1.)  (32, 1.)  (38, 1.) 
> row 20: (2, 1.)  (6, 1.)  (7, 1.)  (9, 1.)  (10, 1.)  (19, 1.)  (20, 1.) 
> row 21: (1, 1.)  (3, 1.)  (14, 1.)  (15, 1.)  (16, 1.)  (17, 1.)  (18, 1.)  (21, 1.)  (23, 1.)  (25, 1.)  (28, 1.)  (30, 1.)  (33, 1.)  (35, 1.) 
> row 22: (0, 1.)  (3, 1.)  (5, 1.)  (11, 1.)  (12, 1.)  (22, 1.)  (26, 1.)  (27, 1.)  (31, 1.)  (32, 1.)  (33, 1.)  (34, 1.) 
> row 23: (0, 1.)  (11, 1.)  (12, 1.)  (13, 1.)  (14, 1.)  (15, 1.)  (18, 1.)  (21, 1.)  (23, 1.)  (27, 1.)  (35, 1.)  (36, 1.) 
> row 24: (0, 1.)  (4, 1.)  (14, 1.)  (19, 1.)  (24, 1.)  (25, 1.)  (28, 1.)  (29, 1.)  (30, 1.)  (37, 1.)  (38, 1.) 
> row 25: (4, 1.)  (6, 1.)  (9, 1.)  (14, 1.)  (15, 1.)  (16, 1.)  (21, 1.)  (24, 1.)  (25, 1.)  (28, 1.)  (30, 1.)  (37, 1.) 
> row 26: (5, 1.)  (8, 1.)  (11, 1.)  (12, 1.)  (13, 1.)  (22, 1.)  (26, 1.)  (27, 1.)  (29, 1.)  (32, 1.)  (39, 1.) 
> row 27: (0, 1.)  (11, 1.)  (12, 1.)  (15, 1.)  (22, 1.)  (23, 1.)  (26, 1.)  (27, 1.)  (35, 1.)  (36, 1.) 
> row 28: (0, 1.)  (4, 1.)  (14, 1.)  (15, 1.)  (21, 1.)  (24, 1.)  (25, 1.)  (28, 1.)  (30, 1.)  (37, 1.) 
> row 29: (8, 1.)  (10, 1.)  (19, 1.)  (24, 1.)  (26, 1.)  (29, 1.)  (32, 1.)  (34, 1.)  (38, 1.)  (39, 1.) 
> row 30: (4, 1.)  (6, 1.)  (8, 1.)  (9, 1.)  (13, 1.)  (16, 1.)  (21, 1.)  (24, 1.)  (25, 1.)  (28, 1.)  (30, 1.)  (37, 1.)  (38, 1.) 
> row 31: (3, 1.)  (5, 1.)  (11, 1.)  (17, 1.)  (18, 1.)  (22, 1.)  (31, 1.)  (33, 1.)  (34, 1.) 
> row 32: (5, 1.)  (7, 1.)  (10, 1.)  (19, 1.)  (22, 1.)  (26, 1.)  (29, 1.)  (32, 1.)  (34, 1.)  (39, 1.) 
> row 33: (1, 1.)  (3, 1.)  (5, 1.)  (17, 1.)  (18, 1.)  (21, 1.)  (22, 1.)  (31, 1.)  (33, 1.)  (34, 1.)  (35, 1.) 
> row 34: (5, 1.)  (7, 1.)  (9, 1.)  (10, 1.)  (13, 1.)  (17, 1.)  (22, 1.)  (29, 1.)  (31, 1.)  (32, 1.)  (33, 1.)  (34, 1.) 
> row 35: (12, 1.)  (13, 1.)  (15, 1.)  (17, 1.)  (18, 1.)  (21, 1.)  (23, 1.)  (27, 1.)  (33, 1.)  (35, 1.)  (36, 1.) 
> row 36: (8, 1.)  (12, 1.)  (13, 1.)  (15, 1.)  (17, 1.)  (18, 1.)  (23, 1.)  (27, 1.)  (35, 1.)  (36, 1.) 
> row 37: (4, 1.)  (24, 1.)  (25, 1.)  (28, 1.)  (30, 1.)  (37, 1.)  (38, 1.) 
> row 38: (4, 1.)  (8, 1.)  (14, 1.)  (19, 1.)  (24, 1.)  (29, 1.)  (30, 1.)  (37, 1.)  (38, 1.)  (39, 1.) 
> row 39: (8, 1.)  (12, 1.)  (26, 1.)  (29, 1.)  (32, 1.)  (38, 1.)  (39, 1.) 
> 
> 
> A native back-tracking gives 8 colors, but all the algorithms in PETSc give 20 colors. Is it supposed to be like this? 
> 
> Fande,
> 
> 
> On Thu, Mar 23, 2017 at 10:50 AM, Hong <hzhang at mcs.anl.gov> wrote:
> Fande,
>  
> I was wondering if the coloring approaches listed online are working? Which ones are in parallel, and which ones are in sequential?
> 
> http://www.mcs.anl.gov/petsc/petsc-current/docs/manualpages/Mat/MatColoringType.html#MatColoringType
>  
>  JP and Greedy are parallel.
> 
> If the coloring is in parallel, can it be used with the finite difference to compute the Jacobian? Any limitations?
>  
> Yes, they work quite well. Git it a try. Let us know if you encounter any problem.
> 
> Hong 
> 
>