EM Seminar: Fast Algos and Parallel Computing

By [ Levent Gürel ]

Solving very large integral equations: incl. biological interaction, THz circuits, radar problems

Metallization thicknesses -> unintended transmitting / receiving antenna: fatal cross-talk

Perforated photonic crystals as wave guides

Diagnosing blood related diseases

Radiating brains with EM waves. Microwaves are not ionizing – don’t alter DNA and cause cancer. But they can raise the temperature of the brain. Is that harmful? EM waves might get focussed in some part. No probes to check, so compute.

Microwave imaging for under the skin tumors (breast cancer)

Model the setup (not working on the hardware) to optimize the imaging method (choice of antenna, placement, etc) Instead of building 100s of setups, they’ll make only 10s.

Types of antenna: vivaldi, spiral, fractal, etc

Antennas in the frame. Model and design before marketing millions of iPhones

Solving Maxwell’s equations accurately. PDEs -> integral equations (Electric/Mag/C/Hybrid Field IE)

Solving for the surface current distribution (J)

Triangular mesh for the geometries (mesh size  = lambda / 10)

To matrix equations: known basis functions and unknown coefficients

Families of testing and basis functions: http://en.wikipedia.org/wiki/Galerkin_method

Small piece of function radiating with the Green’s function -> ∫ -> electric field radiated by the current element. Two triangles (testing and basis) (current elements) are interacting.

Back to mesh size: lambda/10 is just a guideline. Millions of triangles -> millions of unknowns. Near neighbor and further interactions. Not sparse, dense. Magnifying Ax = b joke.

How do we solve very large matrix equations? Gaussian elimination, or a variety of decompositions? Nope, iterative methods. (System identification/feedback control again? Woohoo) It can keep the historical data. IIR? Hopefully, these iterations would converge.

Preconditioning to reduce the number of iterations.

Choice of pre-conditioners and iterative solvers depends on the problem:


n^2 operations for multiplying a matrix and a vector. Multilevel fast multipole algorithm. CG, QMR, GMRES, LSQ etc


Neighborhoods and aggregation. Add contribution to E of all basis in a neighborhood. Then distribute this aggregated field to the cluster of testing functions. n^1.5 and 3-step process. Network theory analogy. UPS truck coming to your house, getting all the packets in a central location, and distribute them later in Houston.

Multi-level: Put the object in a box. Tree structure and boxes. Grandparents, parents and children.

Segregation: level up -> translation -> level down: desegregation. n log(n) — almost like n^1

ED: helmholtz, electrostatics, MD!!!, etc.


How do we solve the biggest problems without the strongest computers? Simple Gaussian elimination (n^3 — not anymore.)

Better algorithm. Then, use parallel computing.

Take a simple geometry and compare the computed answer with the analytical solution. More confidence in a text output consisting of millions of complex numbers

Split ring resonators. Unit cells in 3D arrays. Incoming wavelength bigger than the scale: metamaterials have funny properties

Split-Ring Resonator walls for shielding? These are like notch filters. Stop band in the transmission.

Close off the splits -> all pass filter. Thin wire array -> no pass (provided spacing is small compared to wavelength -> you don’t need a solid conductor) Careful with the polarization. Perpendicular to “jail bars” will pass.

Ferridite cage with SRRs? Like a gate.

NASA Almond problem.

Hardware and GPUs.

Kernel based solver (Laplace/gravity etc) vs algebraic (Hackbusch)

Small structures compared to wavelength – FMM would get problems

Going below n^2: taking advantage of redundancies in the matrix. These redundancies even more in low frequency problems. Try ACA.

Adding more processors? Well, efficiency of parallelization goes down, and we work on these inefficiencies, and make incremental improvements

Think of geometries, not material properties. We have surfaces, and we can go up to a billion unknowns.

Bottleneck: RAM (~2 TB) Storage: order of n. Memory: order n log(n)

Communications / nodes is an efficiency killer. Perfecting parallel programming there.

The rank of the matrix equation should be n. Take a sub-block, say 100×100. Its rank is probably lesser. No free lunch – approximations (use them where you CAN get by) An error controllable method.

HF physical optics. Open surface problems vs cavity problems. With the physical systems, we can throw a lot of the things away.

Compute Henkel and Basal functions carefully. Not relying on standard libraries.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s