THE PARALLELIZATION OF HELMHOLTZ EQUATION RELATED TO BREAST CANCER GROWTH ASNIDA CHE ABD GHANI UNIVERSITI TEKNOLOGI MALAYSIA THE PARALLELIZATION OF HELMHOLTZ EQUATION RELATED TO BREAST CANCER GROWTH ASNIDA CHE ABD GHANI A thesis submitted in fulfilment of the requirements for the award of the degree of Master of Science (Mathematics) Faculty of Science Universiti Teknologi Malaysia MAY 2015 iii To my beloved parents, siblings and friends. iv ACKNOWLEDGEMENTS First and foremost, I would like to thank Allah Almighty for His guidance and help in giving me the strength to complete this thesis. A special thanks to my supervisor, Associate Professor Dr. Norma binti Alias for her constructive advice and idea throughout the period of this research project. I would like to express my thanks to Ministry of Higher Education for the financial support through MyBrain. I also acknowledge my debt to the examiners, Prof. Dr. Arsmah Iblahim and Dr. Yeak Su Hoe for devoting their time generously reading my thesis. I am also indebted to my beloved mother, Rohana Musa and siblings, Arman, Asniza, Arimi, Hazilah and Arif, who are my source of inspiration for their continuous encouragement and many sacrifices. The writing of this thesis would have been impossible without the moral support and love from my family. To them, I extend my sincere thanks. Thanks are also due to all my dearest friends, Hafizah Farhah, Maizatul Nadhirah, Izdihar and family who watched me fumble my way to this thesis. Finally, I would like toexpress my sincere appreciation to all who have helped me in one way or another,but whose names are not mentioned. v ABSTRACT Detecting breast cancer at an early stage will decrease the mortality rate and improve the cancer treatment successfully. This research focuses on the parallelization of the mathematical modeling on breast cancer growth using one and two dimensional Helmholtz equations. Finite difference method (FDM) is chosen to discretize the Helmholtz equation in order to generate a large sparse grid solution. Some numerical iterative methods are used to simulate the grid solution. The numerical methods under consideration are alternating group explicit (AGE), Red Black Gauss Seidel (RBGS), Gauss Seidel (GS) and Jacobi (JB) method. The alternative numerical method can be detected and quantified by comparing and analyzing the numerical methods under consideration in the aspect of run time, number of iterations, maximum error, root mean square error and computational complexity. Domain decomposition technique of the parallel AGE, RBGS and JB can be applied to decompose the full domain solution into subdomains. The message passing among the neighbourhood of subdomain can be done efficiently using MATLAB Distributed Computing Software. This technique is a straight forward implementation on a distributed parallel computer system (DPCS) because of the non-overlapping subdomain feature. The computer system architecture of DPCS is a single instruction multiple data stream (SIMD) and well suited to support the high computational complexity of a large sparse matrix. The development of DPCS is based on the Linux platform with eight processors of Intel® Core™ Duo Processor architecture and MATLAB Distributed Computing Software version R2011a. The visualization of one and two dimensional of breast cancer growth are captured using Comsol Multiphysic version 4.3a. The parallel performance evaluations of parallel AGE, RBGS and JB are measured in terms of run time, speedup, efficiency, effectiveness and temporal performance. As a conclusion, the parallel algorithm of AGE is superior than RBGS, GS and JB for solving one and two dimensional Helmholtz equations for breast cancer growth early detection. vi ABSTRAK Pengesanan kanser payudara pada peringkat awal akan mengurangkan kadar kematian dan meningkatkan rawatan kanser dengan jayanya. Kajian ini memberi tumpuan kepada penyelarian model matematik ke atas pertumbuhan kanser payudara menggunakan persamaan Helmholtz berdimensi satu dan dua. Kaedah beza terhingga (FDM) dipilih untuk mendiskrit persamaan Helmholtz dengan menjana penyelesaian grid jarang yang besar. Beberapa kaedah lelaran berangka digunakan untuk mensimulasikan penyelesaian grid. Kaedah berangka yang dipertimbangkan adalah kaedah kumpulan selang-seli tak tersirat (AGE), kaedah Gauss Seidel Merah Hitam (RBGS), kaedah Gauss Seidel (GS) dan kaedah Jacobi (JB). Kaedah alternatif berangka dapat dikesan dan diukur dengan membanding dan menganalisis kaedah berangka yang dipertimbangkan dalam aspek masa, bilangan lelaran, ralat maksimum, ralat punca min kuasa dua dan kerumitan pengiraan. Teknik penguraian domain AGE, RBGS dan JB digunakan untuk mengurai penyelesaian domain penuh ke dalam beberapa subdomain. Mesej yang dihantar melalui subdomain berdekatan boleh dilakukan dengan cekap menggunakan Perisian Pengkomputeran Teragih MATLAB. Teknik ini adalah pelaksanaan terus di dalam sistem komputer teragih selari (DPCS) kerana ciri subdomain yang tidak bertindih. Senibina sistem komputer DPCS merupakan arahan tunggal pelbagai aliran data (SIMD) dan didapati sesuai untuk menyokong pengiraan matriks jarang yang besar lagi rumit. Pembangunan DPCS adalah berdasarkan pada platform Linux dengan lapan pemproses senibina Intel ® Core ™ Duo dan Perisian Pengkomputeran Teragih versi R2011a MATLAB. Gambaran satu dan dua dimensi pertumbuhan kanser payudara dirakam dengan menggunakan Comsol Multiphysic versi 4.3a. Penilaian prestasi selari AGE, RBGS dan JB diukur dari segi masa, kecepatan, kecekapan, keberkesanan dan prestasi sementara. Kesimpulannya, algoritma selari AGE adalah lebih baik daripada kaedah RBGS, GS dan JB untuk menyelesaikan persamaan Helmholtz berdimensi satu dan dua bagi pengesanan awal pertumbuhan kanser payudara. vii TABLE OF CONTENTS CHAPTER TITLE PAGE DECLARATION ii DEDICATION iii ACKNOWLEDGEMENT iv ABSTRACT v ABSTRAK vi TABLE OF CONTENTS vii LIST OF TABLES x LIST OF FIGURES xi LIST OF SYMBOLS xiii LIST OF APPENDICES xiv 1.0 INTRODUCTION 1 1.1 Introduction 1 1.1.1 Breast Cancer Growth 2 1.1.2 Finite Difference Method 3 1.1.3 Distributed Parallel Computer System 4 1.1.4 Parallel Computer Platform 7 1.1.5 Parallel Performance Evaluation 10 1.2 Helmholtz Equation 12 1.3 Research Objectives 13 1.4 The Scope of Study 14 1.5 The Outline 15 viii 2.0 HELMHOLTZ EQUATION 17 2.1 Introduction 17 2.2 Helmholtz equation 17 2.3 Discretization 20 2.3.1 One Dimensional 22 2.3.2 Two Dimensional 26 2.4 Convergence of Classical Numerical Methods 28 2.5 MRI Edge Detection 30 2.6 Chapter Conclusion 31 3.0 SEQUENTIAL ALGORITHM 32 3.1 Introduction 32 3.2 One Dimensional 32 3.2.1 AGE Douglas Method 34 3.2.2 AGE Brian Method 46 3.2.3Red Black Gauss Seidel 53 3.2.4 Gauss Seidel Method 55 3.2.5 Jacobi Method 56 3.3 Two dimensional 58 3.3.1 AGED Method 58 3.3.2 AGEB Method 63 3.3.3RBGS Method 66 3.3.4 Gauss Seidel Method 67 3.3.5 Jacobi Method 68 3.4 Chapter Conclusion 69 4.0 PARALLEL ALGORITHMS 70 4.1 Introduction 70 4.2 One dimensional 72 4.2.1 Parallel AGED Method 81 ix 4.2.2 Parallel AGEB Method 83 4.2.3 Parallel Jacobi method 85 4.2.4 Parallel Red Black Gauss Seidel method 87 4.3 Chapter Conclusion 88 5.0 NUMERICAL RESULTS AND DISCUSSION 90 5.1 Introduction 90 5.2 Numerical Results 91 5.3 Parallel Performance Evaluation 95 5.4 Chapter Conclusion 104 6.0 CONCLUSION 106 6.1 Introduction 106 6.2 Conclusion 106 6.3 Suggestions for Future Research 108 REFERENCES 110 Appendices A-C 116-125 x LIST OF TABLES TABLE NO. TITLE PAGE 1.1 Classifications of parallel computer architecture 5 1.2 The parallel command in MDC 9 5.1 Performance analysis for 1D sequential algorithms 91 5.2 Computational complexity for 1D sequential 92 algorithm 5.3 Performance analysis for 2D sequential algorithms 94 5.4 Computational complexity for 2D sequential 95 algorithm 5.5 Parallel performance evaluations of PAGEB, 96 PAGED, PRBGS and PJB based on run time, speedup, efficiency, effectiveness and temporal performance 5.6 The parallel performance evaluation of PAGEB 97 5.7 The parallel performance evaluation of PAGED 98 5.8 The parallel performance evaluation of PRBGS 99 5.9 The parallel performance evaluation of PJB 101