Nested dissection
ಸಂಖ್ಯಾತ್ಮಕ ವಿಶ್ಲೇಷಣೆಯಲ್ಲಿ, ಗ್ರಾಫ್ ವಿಭಜನೆಯ ಆಧಾರದ ಮೇಲೆ ರೇಖೀಯ ಸಮೀಕರಣಗಳ ವಿರಳ ಸಮ್ಮಿತೀಯ ವ್ಯವಸ್ಥೆಗಳ ಪರಿಹಾರಕ್ಕಾಗಿ ನೆಸ್ಟೆಡ್ ವಿಭಜನೆಯು ವಿಭಜನೆ ಮತ್ತು ವಶಪಡಿಸಿಕೊಳ್ಳುವ ಶೋಧಕವಾಗಿದೆ. ನೆಸ್ಟೆಡ್ ಡಿಸ್ಸೆಕ್ಷನ್ ಅನ್ನು ಗ್ಯಾರೆಟ್ ಬಿರ್ಖಾಫ್ ಅವರು ಪರಿಚಯಿಸಿದರು. ನೆಸ್ಟೆಡ್ ಡಿಸ್ಸೆಕ್ಷನ್ ಈ ಕೆಳಗಿನ ಹಂತಗಳನ್ನು ಒಳಗೊಂಡಿದೆಃ ದಿಕ್ಕಿಲ್ಲದ ರೇಖಾಚಿತ್ರವನ್ನು ರಚಿಸಿ, ಇದರಲ್ಲಿ ಶೃಂಗಗಳು ರೇಖಾತ್ಮಕ ಸಮೀಕರಣಗಳ ವ್ಯವಸ್ಥೆಯ ಸಾಲುಗಳು ಮತ್ತು ಕಾಲಮ್ಗಳನ್ನು ಪ್ರತಿನಿಧಿಸುತ್ತವೆ, ಮತ್ತು ಅಂಚು ವ್ಯವಸ್ಥೆಯನ್ನು ಪ್ರತಿನಿಧಿಸುವ ವಿರಳ ಮ್ಯಾಟ್ರಿಕ್ಸ್ನಲ್ಲಿ ಶೂನ್ಯವಲ್ಲದ ನಮೂದನ್ನು ಪ್ರತಿನಿಧಿಸುತ್ತದೆ. ವಿಭಜಕಗಳನ್ನು ಬಳಸಿಕೊಂಡು ಗ್ರಾಫ್ ಅನ್ನು ಪುನರಾವರ್ತಿತವಾಗಿ ಉಪಗ್ರಾಫ್ಗಳಾಗಿ ವಿಭಜಿಸಿ, ಶೃಂಗಗಳ ಸಣ್ಣ ಉಪಗುಂಪುಗಳನ್ನು ತೆಗೆದುಹಾಕುವುದರಿಂದ ಗ್ರಾಫ್ ಅನ್ನು ಉಪಗ್ರಾಫ್ಗಳಾಗಿ ವಿಂಗಡಿಸಲು ಅನುವು ಮಾಡಿಕೊಡುತ್ತದೆ, ಇದು ಶೃಂಗಗಳ ಸಂಖ್ಯೆಯ ಸ್ಥಿರವಾದ ಭಾಗವನ್ನು ಹೊಂದಿರುತ್ತದೆ. ವಿಭಜನೆಯ ಪುನರಾವರ್ತಿತ ರಚನೆಯಿಂದ ಅಸ್ಥಿರಗಳನ್ನು ತೆಗೆದುಹಾಕಲು ಆದೇಶಿಸುವ ಮೂಲಕ ಚೋಲ್ಸ್ಕಿ ವಿಭಜನೆಯನ್ನು (ಸಮ್ಮಿತೀಯ ಮ್ಯಾಟ್ರಿಕ್ಸ್ಗಳಿಗೆ ಗಾಸಿಯನ್ ಎಲಿಮಿನೇಷನ್ನ ಒಂದು ರೂಪಾಂತರ) ನಿರ್ವಹಿಸಿಃ ವಿಭಜಕವನ್ನು ತೆಗೆದುಹಾಕುವ ಮೂಲಕ ರೂಪುಗೊಂಡ ಎರಡು ಉಪಗ್ರಾಫ್ಗಳಲ್ಲಿ ಪ್ರತಿಯೊಂದನ್ನು ಮೊದಲು ತೆಗೆದುಹಾಕಲಾಗುತ್ತದೆ ಮತ್ತು ನಂತರ ವಿಭಜಕದ ಶೃಂಗಗಳನ್ನು ತೆಗೆದುಹಾಕಲಾಗುತ್ತದೆ. ಈ ಅಲ್ಗಾರಿದಮ್ನ ಪರಿಣಾಮವಾಗಿ, ಫಿಲ್-ಇನ್ (ಇನ್ಪುಟ್ ಮ್ಯಾಟ್ರಿಕ್ಸ್ ರಚನೆಯ ಭಾಗವಾಗಿರದ ಕೊಲೆಸ್ಕಿ ವಿಭಜನೆಯಲ್ಲಿ ರಚಿಸಲಾದ ಶೂನ್ಯವಲ್ಲದ ಮ್ಯಾಟ್ರಿಕ್ಸ್ ನಮೂದುಗಳ ಸೆಟ್) ಪುನರಾವರ್ತಿತ ವಿಭಾಗದ ಪ್ರತಿ ಹಂತದಲ್ಲೂ ವಿಭಜಕದ ಗಾತ್ರದ ಗರಿಷ್ಠ ವರ್ಗಕ್ಕೆ ಸೀಮಿತವಾಗಿದೆ. ನಿರ್ದಿಷ್ಟವಾಗಿ, ಪ್ಲ್ಯಾನರ್ ಗ್ರಾಫ್ಗಳಿಗೆ (ಎರಡು ಆಯಾಮದ ಸೀಮಿತ ಅಂಶ ವಿಧಾನದ ಜಾಲರಿಗಳಿಂದ ಪಡೆದ ವಿರಳ ರೇಖೀಯ ವ್ಯವಸ್ಥೆಗಳ ಪರಿಹಾರದಲ್ಲಿ ಆಗಾಗ್ಗೆ ಉದ್ಭವಿಸುವ) ಪರಿಣಾಮವಾಗಿ ಮ್ಯಾಟ್ರಿಕ್ಸ್ ಒ (ಎನ್ ಲಾಗ್ ಎನ್) ನಾನ್ಜೆರೋಸ್ ಅನ್ನು ಹೊಂದಿರುತ್ತದೆ, ಏಕೆಂದರೆ ಪ್ಲ್ಯಾನರ್ ವಿಭಜಕ ಪ್ರಮೇಯವು ಒ () ಗಾತ್ರದ ವಿಭಜಕಗಳನ್ನು ಖಾತರಿಪಡಿಸುತ್ತದೆ. ಅನಿಯಂತ್ರಿತ ಗ್ರಾಫ್ಗಳಿಗೆ, ನೆಸ್ಟೆಡ್ ಡಿಸ್ಸೆಕ್ಷನ್ ಇದೆ, ಅದು ಆಪ್ಟಿಮಲ್ನ ಅಂಶದೊಳಗೆ ಭರ್ತಿ ಮಾಡುವುದನ್ನು ಖಾತರಿಪಡಿಸುತ್ತದೆ, ಅಲ್ಲಿ d ಗರಿಷ್ಠ ಡಿಗ್ರಿ ಮತ್ತು m ಶೂನ್ಯವಲ್ಲದ ಸಂಖ್ಯೆಯಾಗಿದೆ. ಗ್ರಾಫ್ನ ಸೈಕಲ್ ಶ್ರೇಣಿಯನ್ನು ಅಥವಾ ಸಮ್ಮಿತೀಯ ಬೂಲಿಯನ್ ಮ್ಯಾಟ್ರಿಕ್ಸ್ ಅನ್ನು ಸಹ ನೋಡಿ, ಇದು ಕೊಲೆಸ್ಕಿ ವಿಭಜನೆ ವೆರ್ಟೆಕ್ಸ್ ವಿಭಜಕ ಟಿಪ್ಪಣಿಗಳ ಉಲ್ಲೇಖಗಳನ್ನು ನಿರ್ವಹಿಸಲು ಅಗತ್ಯವಾದ ಕನಿಷ್ಠ ಸಮಾನಾಂತರ ಸಮಯವನ್ನು ಅಳೆಯುತ್ತದೆ. .. .. .. .. ವಿರಳ ಮ್ಯಾಟ್ರಿಕ್ಸ್ಗಳು ಸಂಖ್ಯಾತ್ಮಕ ರೇಖೀಯ ಬೀಜಗಣಿತ