[petsc-users] coloring algorithms

[Kong, Fande]

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
>> <https://urldefense.proofpoint.com/v2/url?u=http-3A__www.mcs.anl.gov_petsc_petsc-2Dcurrent_docs_manualpages_Mat_MatColoringType.html-23MatColoringType&d=DwMFaQ&c=54IZrppPQZKX9mLzcGdPfFD1hxrcB__aEkJFOKJFd00&r=DUUt3SRGI0_JgtNaS3udV68GRkgV4ts7XKfj2opmiCY&m=P_6UFiOZ_X1dqcVpUO4Ofk5qw7LX1j67-B1jDTDh2V4&s=OUAGH3fmoF-nvAjjE2JOuU7p0GX5H2twdeZEu2kgeD8&e=>
>>
>
>  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
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.mcs.anl.gov/pipermail/petsc-users/attachments/20170323/04f661f0/attachment.html>