home *** CD-ROM | disk | FTP | other *** search
/ Liren Large Software Subsidy 10 / 10.iso / l / l460 / 3.ddi / DEMOS.DI$ / SEPDEMO.M < prev    next >
Encoding:
Text File  |  1993-03-07  |  2.7 KB  |  90 lines
  1. %SEPDEMO Orderings and separators for a finite element mesh.
  2.  
  3. %    John Gilbert, 3-10-91.
  4. %    Copyright (c) 1984-93 by The MathWorks, Inc.
  5.  
  6. load('crack.mat')
  7. A = crack;
  8. xy = xy;
  9.  
  10. clf;
  11.  
  12. gplot(A,xy);
  13. title('Finite Element Mesh')
  14.  
  15. clc;
  16. disp(' ');
  17. disp('This script shows several different orderings of a matrix');
  18. disp('corresponding to the finite element mesh you see. ');
  19. disp(' ');
  20. disp('Each ordering generates an "elimination tree" which describes  ');
  21. disp('the dependencies among the columns of the reordered matrix. ');
  22. disp('The elimination tree in turn induces a divide-and-conquer ');
  23. disp('block decomposition of the matrix. ');
  24. disp(' ');
  25. disp('You might want to expand the plot window for the rest of the demo. ')
  26. disp(' ');
  27. disp('Press any key to continue. ');
  28. pause;
  29. clc;
  30.  
  31. disp(' ');
  32. disp('The highlighted separator in the mesh is the last diagonal block ');
  33. disp('of the matrix, and also the path of only children from the root ');
  34. disp('of the elimination tree.  Each connected component of the rest ');
  35. disp('of the mesh is another diagonal block, and is a subtree of the ');
  36. disp('elimination tree. ');
  37. disp(' ');
  38. disp('Minimum degree is a heuristic that builds the elimination tree ');
  39. disp('from the bottom up by a greedy algorithm.  We will see two');
  40. disp('versions, corresponding to different parameter settings. ');
  41. disp(' ');
  42.  
  43. spparms('default');
  44. p = symmmd(A);
  45. sepplot(A(p,p),xy(p,:),'Loose Minimum Degree Order','Loose Min Deg');
  46.  
  47. disp(' ');
  48. disp('Press any key to continue. ');
  49. pause;
  50. clc;
  51.  
  52. disp(' ');
  53. disp('Now we use a slightly different version of minimum degree. ');
  54. disp(' ');
  55. spparms('tight')
  56. p = symmmd(A);
  57. spparms('default')
  58. sepplot(A(p,p),xy(p,:),'Tight Minimum Degree Order','Tight Min Deg');
  59.  
  60. disp(' ');
  61. disp('Press any key to continue. ');
  62. pause;
  63. clc;
  64.  
  65. % disp(' ');
  66. % disp('The next order is Sparspak''s nested dissection order, which builds the ');
  67. % disp('elimination tree from the top down by trying to find good separators. ');
  68. % disp(' ');
  69. % disp('(This will only work if you have Sparspak running on your machine.) ');
  70. % disp(' ');
  71. % p = spknd(A);
  72. % sepplot(A(p,p),xy(p,:),'Nested Dissection Order','Nested Dissection');
  73. % 
  74. % disp(' ');
  75. % disp('Press any key to continue. ');
  76. % pause;
  77. % clc;
  78.  
  79. disp(' ');
  80. disp('Finally, for comparison, we show a heuristic called ');
  81. disp('reverse Cuthill-McKee that tries to reduce the profile');
  82. disp('of the matrix, or cluster the nonzeros near the diagonal.');
  83. disp('RCM sometimes gives sparse factors, but it also tends to  ');
  84. disp('give an unbalanced or even trivial separator partition. ');
  85. disp(' ');
  86. p = symrcm(A);
  87. sepplot(A(p,p),xy(p,:),'Reverse Cuthill-McKee Order','RCM');
  88.  
  89. disp('End')
  90.