The Multilevel Fast Multipole Algorithm (MLFMA) for Solving Large-Scale Computational Electromagnetics Problems E-Book

Ozgur Ergul

• Herausgeber: John Wiley & Sons
• Kategorie: Wissenschaft und neue Technologien
• Serie: IEEE/OUP Series on Electromagnetic Wave Theory (formerly IEEE only), Series Editor: Donald G. Dudley.
• Sprache: Englisch

Seitenzahl: 520

Veröffentlichungsjahr: 2014

Beschreibung

The Multilevel Fast Multipole Algorithm (MLFMA) for Solving Large-Scale Computational Electromagnetic Problems provides a detailed and instructional overview of implementing MLFMA. The book: * Presents a comprehensive treatment of the MLFMA algorithm, including basic linear algebra concepts, recent developments on the parallel computation, and a number of application examples * Covers solutions of electromagnetic problems involving dielectric objects and perfectly-conducting objects * Discusses applications including scattering from airborne targets, scattering from red blood cells, radiation from antennas and arrays, metamaterials etc. * Is written by authors who have more than 25 years experience on the development and implementation of MLFMA The book will be useful for post-graduate students, researchers, and academics, studying in the areas of computational electromagnetics, numerical analysis, and computer science, and who would like to implement and develop rigorous simulation environments based on MLFMA.

Leseprobe

Table of Contents

Cover

Series Page

Title Page

Copyright

Preface

List of Abbreviations

Chapter 1: Basics

1.1 Introduction

1.2 Simulation Environments Based on MLFMA

1.3 From Maxwell's Equations to Integro-Differential Operators

1.4 Surface Integral Equations

1.5 Boundary Conditions

1.6 Surface Formulations

1.7 Method of Moments and Discretization

1.8 Integrals on Triangular Domains

1.9 Electromagnetic Excitation

1.10 Multilevel Fast Multipole Algorithm

1.11 Low-Frequency Breakdown of MLFMA

1.12 Iterative Algorithms

1.13 Preconditioning

1.14 Parallelization of MLFMA

Chapter 2: Solutions of Electromagnetics Problems with Surface Integral Equations

2.1 Homogeneous Dielectric Objects

2.2 Low-Contrast Breakdown and Its Solution

2.3 Perfectly Conducting Objects

2.4 Composite Objects with Multiple Dielectric and Metallic Regions

2.5 Concluding Remarks

Chapter 3: Iterative Solutions of Electromagnetics Problems with MLFMA

3.1 Factorization and Diagonalization of the Green's Function

3.2 Multilevel Fast Multipole Algorithm

3.3 Lagrange Interpolation and Anterpolation

3.4 MLFMA for Hermitian Matrix-Vector Multiplications

3.5 Strategies for Building Less-Accurate MLFMA

3.6 Iterative Solutions of Surface Formulations

3.7 MLFMA for Low-Frequency Problems

3.8 Concluding Remarks

Chapter 4: Parallelization of MLFMA for the Solution of Large-Scale Electromagnetics Problems

4.1 On the Parallelization of MLFMA

4.2 Parallel Computing Platforms for Numerical Examples

4.3 Electromagnetics Problems for Numerical Examples

4.4 Simple Parallelizations of MLFMA

4.5 The Hybrid Parallelization Strategy

4.6 The Hierarchical Parallelization Strategy

4.7 Efficiency Considerations for Parallel Implementations of MLFMA

4.8 Accuracy Considerations for Parallel Implementations of MLFMA

4.9 Solutions of Large-Scale Electromagnetics Problems Involving PEC Objects

4.10 Solutions of Large-Scale Electromagnetics Problems Involving Dielectric Objects

4.11 Concluding Remarks

Chapter 5: Applications

5.1 Case Study: External Resonances of the Flamme

5.2 Case Study: Realistic Metamaterials Involving Split-Ring Resonators and Thin Wires

5.3 Case Study: Photonic Crystals

5.4 Case Study: Scattering from Red Blood Cells

5.5 Case Study: Log-Periodic Antennas and Arrays

5.6 Concluding Remarks

Appendix

A.1 Limit Part of the Operator

A.2 Post Processing

A.3 More Details of the Hierarchical Partitioning Strategy

A.4 Mie-Series Solutions

A.5 Electric-Field Volume Integral Equation

A.6 Calculation of Some Special Functions

References

Index

End User License Agreement

Pages

xi

xiii

xiv

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

53

55

54

56

57

58

59

60

61

62

63

64

65

66

67

69

68

70

71

72

73

74

75

77

76

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

100

99

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

122

121

123

124

125

126

127

128

130

129

131

132

133

134

135

136

137

138

139

140

141

142

143

146

144

145

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

205

204

206

208

207

209

211

210

212

213

214

216

217

215

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

252

251

253

254

255

256

257

258

259

260

261

262

263

268

264

265

266

267

269

270

271

272

273

274

275

277

276

278

279

280

281

283

282

284

285

286

287

288

289

290

291

293

292

294

295

296

297

298

299

300

301

302

303

304

305

306

307

309

308

310

311

312

313

314

315

317

316

318

319

320

321

322

323

324

325

326

327

328

329

330

331

332

333

334

335

336

337

338

339

340

341

342

343

344

345

346

347

348

349

350

351

352

353

354

355

356

357

358

359

360

361

362

363

364

365

366

368

367

441

442

443

444

445

446

447

448

449

450

451

452

453

454

455

Guide

Cover

Table of Contents

Preface

Chapter 1: Basics

List of Illustrations

Figure 1.1

Figure 1.2

Figure 1.3

Figure 1.4

Figure 1.5

Figure 1.6

Figure 1.7

Figure 1.8

Figure 1.9

Figure 1.10

Figure 1.11

Figure 1.12

Figure 1.13

Figure 1.14

Figure 1.15

Figure 1.16

Figure 1.17

Figure 1.18

Figure 1.19

Figure 1.20

Figure 1.21

Figure 1.22

Figure 1.23

Figure 1.24

Figure 1.26

Figure 1.25

Figure 1.27

Figure 1.28

Figure 1.29

Figure 1.30

Figure 2.1

Figure 2.2

Figure 2.3

Figure 2.4

Figure 2.5

Figure 2.6

Figure 2.7

Figure 2.8

Figure 2.9

Figure 2.10

Figure 2.11

Figure 2.12

Figure 2.13

Figure 2.14

Figure 2.15

Figure 2.16

Figure 2.17

Figure 2.18

Figure 2.19

Figure 2.20

Figure 2.21

Figure 2.22

Figure 2.23

Figure 2.24

Figure 2.25

Figure 2.26

Figure 2.27

Figure 2.45

Figure 2.46

Figure 2.47

Figure 2.48

Figure 2.49

Figure 2.50

Figure 2.51

Figure 2.52

Figure 2.53

Figure 2.54

Figure 2.55

Figure 2.56

Figure 2.57

Figure 2.58

Figure 2.59

Figure 2.60

Figure 2.61

Figure 2.62

Figure 2.63

Figure 2.64

Figure 2.65

Figure 2.66

Figure 2.67

Figure 2.68

Figure 2.69

Figure 3.1

Figure 3.2

Figure 3.3

Figure 3.4

Figure 3.5

Figure 3.6

Figure 3.7

Figure 3.8

Figure 3.9

Figure 3.10

Figure 3.11

Figure 3.12

Figure 3.13

Figure 3.14

Figure 3.15

Figure 3.16

Figure 3.17

Figure 3.18

Figure 3.19

Figure 3.20

Figure 3.21

Figure 3.22

Figure 3.23

Figure 3.24

Figure 3.25

Figure 3.26

Figure 3.27

Figure 3.28

Figure 3.29

Figure 3.30

Figure 3.31

Figure 3.32

Figure 3.33

Figure 3.34

Figure 3.35

Figure 3.36

Figure 3.37

Figure 3.38

Figure 3.39

Figure 3.40

Figure 3.41

Figure 3.42

Figure 3.43

Figure 3.44

Figure 3.45

Figure 3.46

Figure 4.1

Figure 4.2

Figure 4.3

Figure 4.4

Figure 4.5

Figure 4.6

Figure 4.7

Figure 4.8

Figure 4.9

Figure 4.10

Figure 4.11

Figure 4.12

Figure 4.13

Figure 4.14

Figure 4.15

Figure 4.16

Figure 4.17

Figure 4.18

Figure 4.19

Figure 4.20

Figure 4.21

Figure 4.22

Figure 4.23

Figure 4.24

Figure 4.25

Figure 4.26

Figure 4.27

Figure 4.28

Figure 4.29

Figure 4.30

Figure 4.31

Figure 4.32

Figure 4.33

Figure 4.34

Figure 4.35

Figure 4.36

Figure 4.37

Figure 4.38

Figure 4.39

Figure 4.49

Figure 4.50

Figure 4.51

Figure 4.52

Figure 4.53

Figure 4.55

Figure 4.54

Figure 4.56

Figure 4.58

Figure 4.57

Figure 4.59

Figure 4.63

Figure 4.64

Figure 4.66

Figure 4.65

Figure 4.67

Figure 4.69

Figure 4.68

Figure 4.70

Figure 4.72

Figure 4.73

Figure 4.74

Figure 4.75

Figure 4.76

Figure 4.77

Figure 4.78

Figure 5.1

Figure 5.2

Figure 5.3

Figure 5.4

Figure 5.5

Figure 5.6

Figure 5.7

Figure 5.9

Figure 5.8

Figure 5.10

Figure 5.11

Figure 5.12

Figure 5.13

Figure 5.14

Figure 5.15

Figure 5.16

Figure 5.17

Figure 5.18

Figure 5.19

Figure 5.20

Figure 5.21

Figure 5.22

Figure 5.23

Figure 5.24

Figure 5.25

Figure 5.26

Figure 5.27

Figure 5.28

Figure 5.29

Figure 5.30

Figure 5.31

Figure 5.32

Figure 5.33

Figure 5.34

Figure 5.35

Figure 5.36

Figure A.1

Figure A.2

Figure A.3

Figure A.4

Figure A.5

Figure A.6

Figure A.7

Figure A.8

Figure A.9

List of Tables

Table 2.1

Table 2.2

Table 3.1

Table 3.2

Table 3.3

Table 3.4

Table 3.5

Table 3.6

Table 3.7

Table 3.8

Table 3.9

Table 3.10

Table 3.11

Table 3.12

Table 4.1

Table 4.2

Table 4.3

Table 4.4

Table 4.5

Table 4.6

Table 4.7

Table 4.9

Table 4.10

Table 4.11

Table 4.12

Table 4.13

Table 4.14

Table 5.1

Table A.1

Table A.2

IEEE Press

Hoes Lane

Piscataway, NJ 08854

IEEE Press Editorial Board

Lajos Hanzo, Editor in Chief

R. Abhari

M. El –Hawary

O. P. Malik

J. Anderson

B. - M. Haemmerli

S. Nahavandi

G. W. Arnold

M. Lanzerotti

T. Samad

F. Canavero

D. Jacobson

G. Zobrist

Kenneth Moore, Director of IEEE Book and Information Services (BIS)

IEEE Antenna Propagation Society, Sponsor

APS Liaison to IEEE Press, Robert Mailloux

The Multilevel Fast Multipole Algorithm (MLFMA) for Solving Large-scale Computational Electromagnetics Problems

Özgür Ergül

Middle East Technical University, Turkey

Levent Gürel

Bilkent University, Turkey

IEEE Antennas and Propagation Society, Sponsor

The IEEE Press Series on Electromagnetic Wave Theory Andreas C. Cangellaris, Series Editor

This edition first published 2014

© 2014 John Wiley & Sons, Ltd

Registered office

John Wiley & Sons Ltd, The Atrium, Southern Gate, Chichester, West Sussex, PO19 8SQ, United Kingdom

For details of our global editorial offices, for customer services and for information about how to apply for permission to reuse the copyright material in this book please see our website at www.wiley.com.

The right of the author to be identified as the author of this work has been asserted in accordance with the Copyright, Designs and Patents Act 1988.

All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted, in any form or by any means, electronic, mechanical, photocopying, recording or otherwise, except as permitted by the UK Copyright, Designs and Patents Act 1988, without the prior permission of the publisher.

Wiley also publishes its books in a variety of electronic formats. Some content that appears in print may not be available in electronic books.

Designations used by companies to distinguish their products are often claimed as trademarks. All brand names and product names used in this book are trade names, service marks, trademarks or registered trademarks of their respective owners. The publisher is not associated with any product or vendor mentioned in this book.

Limit of Liability/Disclaimer of Warranty: While the publisher and author have used their best efforts in preparing this book, they make no representations or warranties with respect to the accuracy or completeness of the contents of this book and specifically disclaim any implied warranties of merchantability or fitness for a particular purpose. It is sold on the understanding that the publisher is not engaged in rendering professional services and neither the publisher nor the author shall be liable for damages arising herefrom. If professional advice or other expert assistance is required, the services of a competent professional should be sought.

Library of Congress Cataloging-in-Publication Data applied for.

ISBN: 9781119977414

Preface

This book is about a sophisticated algorithm, namely, the multilevel fast multipole algorithm (MLFMA), which has been developed and improved continuously in the last two decades for the fast and accurate solution of real-life electromagnetics problems. When it was first proposed, MLFMA enabled accurate solutions of problems relating to metallic objects that cannot be solved directly on computers. Since then, the algorithm has been extended to more complicated problems involving metallic, dielectric, and composite objects, has been improved for realistic solutions with unprecedented levels of accuracy, and has been parallelized to handle discretizations involving millions of unknowns. Recently, MLFMA has been the core algorithm to solve the largest dense matrix equations involving more than 1 billion unknowns.

Due to high academic and industrial impacts, computational simulations of electromagnetic phenomena have attracted the interest of many researchers. The literature includes excellent studies involving huge efforts to develop novel solvers for more efficient and accurate simulations. Along this direction, MLFMA has been one of the major algorithms that have passed the time test. Since it was proposed, this algorithm has proved its robustness, efficiency, and accuracy in many simulations involving diverse components and parameters. Today, most of the leading research centers now have their own implementations of MLFMA, for sequential and/or parallel platforms, among their code libraries. Unsurprisingly, MLFMA has also attracted the interest of industrial bodies via commercial programs using the high potential of the algorithm. And, more importantly, due to its superior efficiency and robustness, MLFMA will definitely be one of the key algorithms of computational electromagnetics in the future.

This book provides a detailed and instructional overview of MLFMA for post-graduate students, researchers, and academics, studying in the areas of computational electromagnetics, numerical analysis, and computer science.

December 2011

List of Abbreviations

AMLFMA:

Approximate multilevel fast multipole algorithm

BCE:

Boundary-condition error

BDP:

Block-diagonal preconditioner

BiCG:

Biconjugate gradient (method)

BiCGStab:

Biconjugate gradient stabilized (method)

CFIE:

Combined-field integral equation

CG:

Conjugate gradient (method)

CGS:

Conjugate gradient squared (method)

CMM:

Composite metamaterial

CTF:

Combined tangential formulation

CNF:

Combined normal formulation

DS-CTF:

Double-stabilized combined tangential formulation

EFIE:

Electric-field integral equation

EFVIE:

Electric-field volume integral equation

FBS-CTF:

Field-based-stabilized combined tangential formulation

FFT:

Fast Fourier transform

FGMRES:

Flexible generalized minimal residual (method)

FMM:

Fast multipole method

GAs:

Genetic algorithms

GMRES:

Generalized minimal residual (method)

HIE:

Hybrid integral equation

ILU:

Incomplete LU

IMLFMA:

Incomplete multilevel fast multipole algorithm

JMCFIE:

Electric and magnetic current combined-field integral equation

LF-MLFMA:

Low-frequency multilevel fast multipole algorithm

LHS:

Left-hand side

LL:

Linear-linear (function)

LOD:

Level of distribution

LP:

Log-periodic (antennas)

LSQR:

Least-squares QR (method)

M-CTF:

Modified combined tangential formulation

MFIE:

Magnetic-field integral equation

MLFMA:

Multilevel fast multipole algorithm

MNMF:

Modified normal Müller formulation

MOM:

Method of moments

MPI:

Message passing interface

MVM:

Matrix-vector multiplication

N-:

Normal

NFP:

Near-field preconditioner

NMF:

Normal Müller formulation

NP:

No-preconditioner (case)

OBSF:

Operator-based-stabilized formulation

QMR:

Quasi-minimal residual (method)

PEC:

Perfect electric conductor

PMCHWT:

Poggio-Miller-Chang-Harrington-Wu-Tsai (formulation)

RBC:

Red blood cell

RCS:

Radar cross section

RHS:

Right-hand side

RMS:

Root mean square

RWG:

Rao-Wilton-Glisson (function)

SAI:

Sparse approximate inverse

S-CNF:

Stabilized combined normal formulation

SCS:

Scattering cross section

S-CTF:

Stabilized combined tangential formulation

SRR:

Split-ring resonator

SWG:

Schaubert-Wilton-Glisson (function)

T-:

Tangential

TFQMR:

Transpose-free quasi-minimal residual (method)

2PBDP:

Two-partition block-diagonal preconditioner

4PBDP:

Four-partition block-diagonal preconditioner

Chapter 1Basics

This chapter presents some of the preliminaries to the multilevel fast multipole algorithm (MLFMA). Using Maxwell's equations and boundary conditions, surface integral equations are derived to formulate electromagnetics problems involving metallic and dielectric objects. Discretizations of the surface integral equations with basis and testing functions on triangular domains lead to dense matrix equations, which can be solved iteratively via MLFMA. Numerical integrations on triangular domains, different types of excitations, iterative algorithms, and preconditioning are also discussed.

1.1 Introduction

Solving electromagnetics problems is extremely important to analyze electromagnetic interactions of electronic devices with each other and with their environments including living and nonliving objects [1]. A plethora of applications in the areas of antennas [2]–[13], radars [14], optics [15], medical imaging [16], wireless communications [17], nanotechnology [18], metamaterials [19]–[25], photonic crystals [26]–[33], remote sensing, and electronic packaging involve scattering and/or radiation of electromagnetic waves. The following are some examples of popular electromagnetics problems: