Special Topics & Applications in Numerical Methods

TAKEAWAYS:

• Finite Element Analysis (FEA) breaks complex systems (e.g., earthquake-resistant buildings) into simpler elements, solving partial differential equations numerically.
• Monte Carlo simulations use random sampling to model uncertainty in finance (e.g., NEPSE stock risk) or logistics (e.g., Pathao driver routing).
• Optimization algorithms (e.g., gradient descent) power recommendation systems (YouTube’s video suggestions) and supply-chain routing (Daraz’s warehouse efficiency).
• Error analysis quantifies inaccuracies in numerical methods (e.g., rounding errors in Khalti’s transaction calculations).
• Parallel computing speeds up large-scale simulations (e.g., NTC’s network traffic modeling) by distributing workloads across processors.
• Machine learning integration uses numerical methods for feature scaling (e.g., preprocessing data for Ncell’s customer churn prediction models).

1. Finite Element Analysis (FEA): Discretizing the Real World

FEA is a numerical technique to approximate solutions to partial differential equations (PDEs) by dividing a continuous domain into smaller, simpler subdomains called finite elements. It is widely used in engineering, physics, and computer graphics.

How FEA Works

1. Discretization: The domain is split into finite elements (e.g., triangles, tetrahedrons).
2. Weak Formulation: PDEs are converted into integral equations (Galerkin method).
3. Assembly: Element equations are combined into a global system.
4. Solution: Solve the system using direct/iterative methods (e.g., Gaussian elimination).
5. Post-processing: Extract results (stress, temperature, etc.) at nodes.

Key Applications in Nepal

Worked Example: 1D Heat Equation

Solve the heat equation $\frac{\partial u}{\partial t}=\alpha \frac{{\partial }^{2}u}{\partial x^2}$ on $x\in [0,1]$ with $u(0,t)=0$, $u(1,t)=100$, and initial condition $u(x,0)=0$. Steps:

1. Discretize $x$ into $N$ elements with spacing $\Delta x=\frac{1}{N}$.
2. Approximate derivatives: $$\frac{{\partial }^{2}u}{\partial x^2}\approx \frac{u_{i+1}-2u_i+u_{i-1}}{(\Delta x{)}^2}$$
3. Use finite difference for time: $$\frac{u_i^{n+1}-u_i^n}{\Delta t}=\alpha \frac{u_{i+1}^n-2u_i^n+u_{i-1}^n}{(\Delta x{)}^2}$$
4. Solve iteratively for $u_i^{n+1}$.

Real-World Tie: NTC uses FEA to model signal propagation in its 4G/5G network towers. By simulating electromagnetic wave behavior across Kathmandu’s terrain, engineers optimize tower placement to minimize dead zones. For example, in the Lalitpur tower project, FEA predicted signal loss in hilly areas, leading to adjusted antenna heights.

2. Monte Carlo Simulations: Randomness as a Tool

Monte Carlo methods rely on random sampling to estimate numerical results, particularly for problems with probabilistic or high-dimensional inputs.

Core Idea

• Law of Large Numbers: The average of many random samples converges to the expected value.
• Central Limit Theorem: Sums of random variables tend toward a normal distribution.

Applications

Worked Example: Estimating π

Use random points in a unit square to estimate $\pi$. Steps:

1. Generate $N$ random points $(x_i,y_i)$ where $x_i,y_i\sim U(0,1)$.
2. Count points inside the quarter-circle $x_i^2+y_i^2\le 1$.
3. Estimate $\pi \approx 4\times \frac{\text{points inside}}{\text{total points}}$.

Real-World Tie: Khalti’s fraud detection uses Monte Carlo simulations to model transaction patterns. By generating synthetic fraudulent transactions and comparing them to real data, Khalti’s algorithm flags anomalies with 95% accuracy. For example, during Dashain sales, Khalti simulated 50,000 fake transactions to train its model, reducing false positives by 30%.

3. Optimization Algorithms: Finding the Best Solution

Optimization seeks to minimize/maximize an objective function subject to constraints. Key methods:

• Gradient Descent: Iteratively update parameters to reduce error (used in machine learning).
• Simulated Annealing: Mimics metal annealing to escape local optima.
• Genetic Algorithms: Evolve solutions via selection, crossover, and mutation.

Comparison Table

Worked Example: Minimizing a Quadratic Function

Minimize $f(x)=x^2+4x+4$ using gradient descent. Steps:

1. Compute gradient: $f^{\prime }(x)=2x+4$.
2. Update rule: $x_{n+1}=x_n-\alpha f^{\prime }(x_n)$, where $\alpha$ is the learning rate.
3. Start at $x_0=5$, $\alpha =0.1$:
   • $x_1=5-0.1\times (2\times 5+4)=2.3$
   • $x_2=2.3-0.1\times (2\times 2.3+4)=-0.16$
   • Converges to $x=-2$ (minimum).

Real-World Tie: Google Maps’ shortest-path algorithm uses a modified Dijkstra’s algorithm (a gradient-like approach) to optimize routes. For example, when you search for "restaurants near me in Thamel," Google’s servers:

1. Treat intersections as nodes and roads as edges.
2. Apply a cost function combining distance, traffic (real-time data from Ncell’s towers), and user preferences.
3. Solve the optimization problem to suggest the fastest route, often avoiding the congested Asan-Teku stretch.

4. Error Analysis: Quantifying Numerical Inaccuracies

Errors in numerical methods arise from:

• Truncation Error: Approximating infinite processes (e.g., Taylor series).
• Rounding Error: Limited precision in floating-point arithmetic.
• Conditioning: Small input changes cause large output changes.

Error Propagation Example

Compute $f(x)=\sqrt{x}$ at $x=2.0$ with 3 decimal precision.

• Exact: $\sqrt{2}\approx 1.414213562$.
• Rounded $x=2.000$: $\sqrt{2.000}=1.414$ (truncation error $\approx 0.0002$).

Real-World Tie: Ncell’s billing system must handle rounding errors when calculating call durations. For example:

• A call lasting 1.999999 seconds might be rounded to 2.000 seconds, adding ₹0.01 to your bill.
• Ncell’s servers use Kahan summation to minimize cumulative rounding errors across millions of transactions daily.

5. Parallel Computing: Speeding Up Simulations

Parallel computing divides a problem into smaller tasks solved simultaneously across processors (e.g., CPUs/GPUs).

Key Techniques

• Domain Decomposition: Split the problem spatially (e.g., FEA for a dam).
• Data Parallelism: Process independent data (e.g., Monte Carlo simulations).
• Task Parallelism: Divide algorithm steps (e.g., gradient descent updates).

Worked Example: Parallel Monte Carlo

Estimate $\pi$ using 4 processors:

1. Divide $N=10,000$ points equally among 4 cores.
2. Each core counts points inside the quarter-circle.
3. Combine results: $\pi \approx 4\times \frac{2500+2490+2510+2500}{10,000}\approx 3.136$.

flowchart TD
    A["Generate N random points"] --> B["Split into 4 subsets"]
    B --> C["Core 1: 2500 points"]
    B --> D["Core 2: 2500 points"]
    B --> E["Core 3: 2500 points"]
    B --> F["Core 4: 2500 points"]
    C --> G["Count inside circle: 625"]
    D --> H["Count inside circle: 622"]
    E --> I["Count inside circle: 627"]
    F --> J["Count inside circle: 625"]
    G & H & I & J --> K["Combine: (625+622+627+625)/10000 ≈ 0.2509"]
    K --> L["π ≈ 4 × 0.2509 ≈ 3.136"]

Real-World Tie: NTC’s 5G network planning uses parallel computing to simulate signal coverage across Nepal. For example:

• A single simulation of 1000 towers would take 24 hours on one CPU.
• Using 8 GPUs, the same task completes in 3 hours, allowing NTC to optimize tower placement before deployment.

6. Machine Learning Integration: Numerical Methods as Backbone

Numerical methods underpin ML algorithms:

• Linear Algebra: Singular Value Decomposition (SVD) for PCA.
• Optimization: Stochastic gradient descent for training.
• Interpolation: Kernel methods in support vector machines.

Example: Feature Scaling in ML

Standardize data using the formula: $$x_{\text{scaled}}=\frac{x-\mu }{\sigma }$$ where $\mu$ is the mean and $\sigma$ is the standard deviation.

Real-World Tie: WhatsApp’s spam detection uses numerical methods to preprocess messages:

1. Tokenization: Split text into words (discrete math).
2. TF-IDF: Convert words to numerical vectors (linear algebra).
3. Logistic Regression: Train a classifier using gradient descent (optimization).

Exam Tip

This unit tests conceptual understanding + real-world connections. Expect:

1. Short-answer questions on definitions (e.g., "Define finite element method").
2. Problem-solving (e.g., "Use Monte Carlo to estimate $e$").
3. Applications (e.g., "How does NTC use FEA?").
4. Code snippets (e.g., Python for gradient descent).

High-scoring strategies:

• Draw diagrams: For FEA meshes, Monte Carlo scatter plots, or optimization paths.
• Link to Nepal: Always tie examples to local tech (e.g., Khalti, NTC, Daraz).
• Show steps: For numerical methods, write out iterations (e.g., gradient descent updates).
• Compare methods: Tables for optimization algorithms or error sources.

Common pitfalls:

• Forgetting units in real-world examples (e.g., "NTC uses FEA" → specify "for signal propagation").
• Skipping error analysis in simulations (always mention truncation/rounding).
• Overcomplicating code (examiners prefer pseudocode for algorithms).

Visual Summary

mindmap
  root((Special Topics in Numerical Methods))
    FEA
      Discretization
      PDEs
      Engineering Applications
    Monte Carlo
      Random Sampling
      π Estimation
      Finance/Logistics
    Optimization
      Gradient Descent
      Simulated Annealing
      ML Training
    Error Analysis
      Truncation
      Rounding
      Conditioning
    Parallel Computing
      Domain Decomposition
      GPU Acceleration
      NTC 5G Example
    ML Integration
      Feature Scaling
      SVD/PCA
      WhatsApp Spam Filter