DEV Community: Patricio Díaz

Numerical Root-Finding Algorithms: Foundations, Theory, and Advanced Methods. Part 1

Patricio Díaz — Sun, 01 Dec 2024 02:22:02 +0000

Root-finding is one of the core problems in computational mathematics. Whether you're solving equations, optimizing functions, or modeling real-world phenomena, the need to find the roots of functions is ubiquitous. This article explores the foundations of root-finding algorithms, their mathematical principles, convergence properties, and real-world applications. Additionally, we will dive into advanced techniques, such as the Secant Method and Brent’s Method, which extend and improve upon traditional approaches.

1. Introduction to Root-Finding Problems

In computational mathematics, finding the root of a function $f (x) = 0$ is essential across a range of fields, from physics and engineering to economics and computer science. A root is simply a value where the function evaluates to zero, and root-finding algorithms are designed to approximate these values when exact solutions are not easily obtainable.

Root-finding problems arise in many contexts:

Solving Equations: For instance, finding the point where the gravitational force equals zero in physics or determining the intersection points of curves in geometry.
Optimization: Algorithms find prices that optimize supply and demand in economics or optimal control points in engineering.
Computer Graphics: Root-finding methods are used in rendering techniques like ray tracing, where finding the intersection of a light ray with 3D surfaces is crucial.

Root-finding algorithms are powerful tools in computational science, particularly when exact analytical solutions to nonlinear equations are unavailable.

2. Fundamental Algorithms Comparison

2.1 Bisection Method

The Bisection Method is one of the most basic and reliable root-finding algorithms. It is based on the intermediate value theorem, which states that if a continuous function $f (x)$ changes sign over an interval $[a, b]$ , then there exists at least one root in the interval.

Mathematical Principles

The method works by repeatedly bisecting the interval and selecting the subinterval that contains the root. The midpoint of the interval, $\frac{a + b}{2}$ , is computed, and the sign of $f (m)$ is checked. If $\cdot f(m) < 0$ , the root lies between $a$ and $m$ , and the interval is updated to $[a, m]$ . If $\cdot f(b) < 0$ , the root lies between $m$ and $b$ , and the interval is updated to $[m, b]$ .

Convergence Characteristics

The Bisection Method is guaranteed to converge provided the function is continuous on the interval and the initial guesses are correctly chosen. The convergence is linear, meaning each step reduces the interval size by half.

Pros and Cons

Pros: Simple to implement, guaranteed convergence if the initial interval is chosen correctly.
Cons: Slow convergence, requiring many iterations to achieve a high degree of accuracy.

2.2 Newton-Raphson Method

The Newton-Raphson Method is a widely used root-finding technique that offers much faster convergence than the Bisection Method, especially when an initial guess is close to the true root. It uses the concept of linear approximation to refine the root estimate.

Mathematical Derivation

The method uses the derivative of the function to find a tangent line at the current approximation. Given an initial guess $x_0$ , the iterative formula is:

x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}

This process continues until the difference between successive approximations is smaller than a specified tolerance.

Convergence Speed

Newton-Raphson has quadratic convergence, meaning that the number of correct digits approximately doubles with each iteration when starting from a sufficiently close guess.

Computational Complexity

The method requires calculating both the function and its derivative at each step, making it computationally expensive compared to methods like Bisection.

Pros and Cons

Pros: Fast convergence (quadratic), efficient for well-behaved functions with a good initial guess.
Cons: Requires the derivative of the function, can fail or diverge if the derivative is zero or the guess is poor.

3. Advanced Root-Finding Algorithms

While the Bisection and Newton-Raphson methods are foundational, they have limitations in certain situations, such as poor initial guesses or the inability to compute derivatives. This has led to the development of more advanced algorithms, such as the Secant Method and Brent’s Method.

3.1 Secant Method

The Secant Method is an improvement on the Newton-Raphson method that does not require the derivative of the function. Instead, it approximates the derivative by using two successive points.

Mathematical Principles

The Secant Method iteratively refines guesses using the following formula:

x_{n+1} = x_n - \frac{f(x_n) \cdot (x_n - x_{n-1})}{f(x_n) - f(x_{n-1})}

Here, the approximation of the derivative is made using the slope of the secant line through

x_n, f(x_n))

and

x_{n-1}, f(x_{n-1}))

Convergence Speed

The Secant Method exhibits superlinear convergence, meaning it converges faster than the Bisection Method but slower than Newton-Raphson.

Pros and Cons

Pros: Does not require the derivative, faster convergence than the Bisection Method.
Cons: Can fail if the two initial guesses are too far apart or if the function behaves erratically.

3.2 Brent’s Method

Brent’s Method is a hybrid algorithm that combines the strengths of the Bisection, Secant, and inverse quadratic interpolation methods. It dynamically selects the most appropriate strategy based on the situation, ensuring robustness and efficiency.

Mathematical Principles

Brent’s Method switches between the following strategies:

Bisection: When the other methods are unreliable.
Secant Method: For faster convergence when appropriate.
Inverse Quadratic Interpolation: Fits a quadratic to three points and solves for its root.

This combination allows the algorithm to reliably find roots even in difficult cases.

Convergence Speed

Brent’s Method generally exhibits superlinear convergence and performs well in a wide range of problems.

Pros and Cons

Pros: Extremely robust, combines the best features of multiple methods, guarantees convergence.
Cons: More complex to implement than simpler methods like Bisection.

4. Real-World Applications of Root-Finding Methods

Root-finding algorithms are crucial in solving real-world computational problems, and the Newton-Raphson Method, with its quadratic convergence, is often the preferred choice when speed and efficiency are required. Its fast convergence makes it highly valuable in many practical applications, particularly where high precision is needed and an initial guess can be reasonably made.

Engineering and Physics: Solving Nonlinear Equations

In fields like engineering and physics, many problems involve solving nonlinear equations to model dynamic systems, equilibrium points, or interactions. For example, in structural engineering, solving for the points at which forces balance within a system often leads to nonlinear equations. Newton-Raphson's rapid convergence makes it ideal for solving such problems where the function is well-behaved, and a good starting guess is available.

In contrast, the Bisection Method is sometimes used in situations where the function is not differentiable or its derivative is hard to compute, but its slower linear convergence can make it impractical when speed is important.

Computer Graphics: Ray Tracing and Geometric Calculations

In computer graphics, where accuracy and speed are essential for rendering, the Newton-Raphson Method is commonly employed for root-finding in 3D rendering algorithms like ray tracing. When computing intersections between light rays and surfaces, for example, Newton-Raphson can quickly hone in on the root, providing the intersection point in a minimal number of iterations, especially when the function is smooth and differentiable.

Though Brent’s Method and the Secant Method can offer reliable solutions in more complex scenarios, when you know the derivative and can make an initial guess, Newton-Raphson will typically outperform them, achieving results in far fewer iterations.

Economics: Solving Market Equilibrium Problems

In economics, finding market equilibrium involves solving nonlinear equations that represent supply and demand curves. The Newton-Raphson Method is often used here for its speed in iteratively refining the estimate of the equilibrium price and quantity, especially when good initial guesses are available. For example, finding the point where supply equals demand often involves solving nonlinear equations that describe complex economic systems.

On the other hand, if the function is difficult to differentiate, or if you're uncertain about the initial guess, the Bisection Method can be a useful fallback, but it is slower, requiring more iterations to arrive at an accurate solution.

5. Choosing the Right Method: Linear vs. Quadratic Convergence

When deciding between the Bisection Method and the Newton-Raphson Method, the key distinction lies in their convergence behavior and the trade-offs between reliability and speed.

Bisection Method: Guaranteed Convergence but Slow

The Bisection Method is a reliable, guaranteed converging method. As long as you can identify an interval where the function changes sign (i.e., $\cdot f(b) < 0$ ), the method will always converge to a root, provided the function is continuous. However, the rate of convergence is linear, meaning that each step only reduces the error by a constant factor, typically halving the interval at each iteration. For a function with a relatively simple form and when you don't have access to the derivative, this method can be quite useful.

However, in scenarios where the precision and speed are paramount (such as real-time computations in engineering, economics, or graphics), Bisection’s slow convergence can become a bottleneck. It requires a larger number of iterations to achieve the same level of accuracy compared to faster methods like Newton-Raphson.

Newton-Raphson Method: Rapid Convergence for Smooth Functions

The Newton-Raphson Method is favored in many applications where faster convergence is required. Its quadratic convergence means that with each iteration, the error is roughly squared (or halved at an exponentially faster rate). This makes it an extremely fast method when the initial guess is close to the true root, as the number of correct digits roughly doubles with each step.

Example of Speed: If the error after 5 iterations is 0.1, after 6 iterations, the error may drop to 0.01, and after 7 iterations, it could be reduced to 0.0001. This rapid convergence is why Newton-Raphson is preferred for solving equations in fields like engineering, where quick, precise solutions are necessary.

However, for the Newton-Raphson Method to work optimally, the function must be smooth and differentiable, and a good initial guess is required. If these conditions are met, the method can vastly outperform slower methods like Bisection.

Caveat: Newton-Raphson can fail or diverge if the initial guess is too far from the root, or if the derivative is small or zero. This is a limitation compared to Bisection, which guarantees convergence but at a slower pace.

When to Choose Which Method

Choose the Bisection Method:
- When the function is continuous but not differentiable.
- When you don’t have access to the derivative.
- When you can find an initial interval where the function changes sign.
- When guaranteed, albeit slow, convergence is necessary.
Choose the Newton-Raphson Method:
- When you have access to the derivative and a reasonable initial guess.
- When rapid convergence and efficiency are required.
- When dealing with smooth, well-behaved functions that allow for reliable derivative computation.

Conclusion

In this article, we have examined the core principles of root-finding algorithms, focusing on two of the most fundamental methods: the Bisection Method and the Newton-Raphson Method. While the Bisection Method is simple, reliable, and guarantees convergence, its linear convergence makes it slow, especially in cases where speed is critical. On the other hand, the Newton-Raphson Method offers quadratic convergence, allowing it to find roots far more quickly and efficiently, provided the function is smooth and a good initial guess is available.

In real-world applications across fields like engineering, computer graphics, and economics, the Newton-Raphson Method is often the preferred choice due to its superior speed and precision. However, the Bisection Method still holds value in scenarios where reliability and guaranteed convergence are more important than speed.

As we move forward in this series, we will explore some real world use cases with their corresponding example code.

Originally posted atNumerical root-finding algorithms: Foundations, theory, and advanced methods. Part 1

Setting up a local Kubernetes environment with Multipass and bridge networking

Patricio Díaz — Wed, 13 Nov 2024 03:13:27 +0000

Introduction

Preparing for the Certified Kubernetes Application Developer (CKAD) certification requires a reliable environment for hands-on practice. While cloud providers are often recommended, setting up a local environment can be more cost-effective and provide valuable learning opportunities. In this guide, I'll walk you through creating a robust local Kubernetes environment using Ubuntu's Multipass and bridge networking.

Why Local Setup?

When I started preparing for my CKAD certification, I wanted an environment that would:

Provide consistent networking between nodes
Allow full control over the infrastructure
Minimize costs compared to cloud solutions
Offer flexibility for experimentation

Hardware Requirements

Before getting started, ensure your system meets these minimum requirements:

Minimum Requirements:

CPU: 4 cores (8 threads recommended)
RAM: 16GB minimum, 32GB recommended
Storage: 100GB free space (SSD recommended)

My Test Environment:

CPU: AMD Ryzen 5 3600 (6 cores, 12 threads)
RAM: 64GB DDR4
Storage: 1TB SSD + 1TB HDD + 750GB HDD

Note: While you can run this setup on lower specifications, you might experience performance issues when running multiple containers and services.

System Compatibility

This guide has been tested on:

Ubuntu 24.10 (host system)
Ubuntu 22.04 LTS (Jammy) for VMs
Multipass 1.14.1
LXD 5.21.2 LTS

While the steps should work on other Ubuntu versions (20.04+), you might encounter slight differences in network interface names or default configurations. If you're using Ubuntu 22.04 or earlier, you may need to modify the networkd configuration syntax slightly.

Network Architecture

Before we dive into the setup, let's understand the network architecture we'll be creating:

Our setup creates multiple network interfaces:

Bridge Network (br0): Primary network for Kubernetes communication
Host Network (enp37s0): Connection to external network
VM Networks: Each VM gets two interfaces
- enp5s0: Multipass default network
- enp6s0: Bridge network interface

Setting Up the Network Bridge

Our first task is creating a dedicated network bridge for our Kubernetes nodes. We'll use systemd-networkd for this purpose, which provides a robust and modern networking stack.

1. Preparing the Network Environment

First, we need to disable NetworkManager and enable systemd-networkd:

# Disable NetworkManager
sudo systemctl stop NetworkManager
sudo systemctl disable NetworkManager

# Enable systemd-networkd
sudo systemctl enable systemd-networkd 
sudo systemctl start systemd-networkd 

# Configure DNS resolution
sudo systemctl enable systemd-resolved
sudo systemctl start systemd-resolved
sudo rm /etc/resolv.conf 
sudo ln -s /run/systemd/resolve/resolv.conf /etc/resolv.conf

2. Configuring the Bridge

We'll create a bridge network with the following specifications:

Network: 172.19.180.0/24
Gateway: 172.19.180.254
DHCP Range: 172.19.180.1 - 172.19.180.253

Create two configuration files in /etc/systemd/network:

Bridge device definition (50-br0.netdev):

[NetDev]
Name=br0
Kind=bridge

Bridge network configuration (51-br0-bind.network):

[Match]
Name=br0

[Network]
Address=172.19.180.254/24
IPForward=yes
ConfigureWithoutCarrier=yes
DHCPServer=yes

[DHCPServer]
PoolSize=253
EmitRouter=yes
EmitDNS=yes
DNS=8.8.8.8

DefaultLeaseTimeSec=600
MaxLeaseTimeSec=7200

[DHCPServerStaticLease]
MACAddress=52:54:00:ab:cd:01
Address=172.19.180.1

[DHCPServerStaticLease]
MACAddress=52:54:00:ab:cd:02
Address=172.19.180.2

3. Enabling IP Forwarding

To allow communication between nodes and the internet:

# enable IP forwarding in the kernel
$ sysctl -w net.ipv4.ip_forward=1
$ sysctl -w net.ipv6.conf.default.forwarding=1

# check
$ sysctl net.ipv4.ip_forward
net.ipv4.ip_forward = 1

$ sysctl net.ipv6.conf.default.forwarding
net.ipv6.conf.default.forwarding = 1

Set forwarding rule for iptables

# Configure iptables to allow forwarding
sudo iptables -P FORWARD ACCEPT
# allow nat forwarding to our bridge
sudo iptables -t nat -A POSTROUTING -o <host-nic> -j MASQUERADE

Optional: Make it permanent

Ubuntu comes with ufw installed by default but it adds lots of restrictions and issues with Multipass regarding DHCP and traffic forwarding so we are going to use plain iptables to manage the firewall rules and make it persistent.

Disclaimer: Follow this steps only if you are sure and did your research about how it will affect your system as they will change the firewall manager for your host. Take this as a suggestion if it works for you.

# to persist the rules after restarts, it will uninstall ufw in the process and save the existing rules
$ sudo apt-get install iptables-persistent

# set default FOrWARD policy to ACCEPT
$ sudo iptables -P FORWARD ACCEPT

# allow nat forwarding for our brigde network. change enp37s0 with your host interface 
$ sudo iptables -t nat -A POSTROUTING -o enp37s0 -j MASQUERADE

# save the rules
$ sudo netfilter-persistent save

# check rules
$ sudo iptables -L
$ sudo iptables -t nat -L

Creating Virtual Machines with Multipass

Multipass provides a lightweight way to create Ubuntu VMs. We'll configure it to work with our bridge network.

1. Setting Up Multipass with LXD

snap install lxd
snap connect multipass:lxd lxd
multipass set local.driver=lxd

2. Launching Kubernetes Nodes

# Control plane node
multipass launch jammy \
    --name ckad-cp \
    --cpus 2 \
    --memory 8G \
    --disk 20G \
    --network name=br0,mode=auto,mac=52:54:00:ab:cd:01

# Worker node
multipass launch jammy \
    --name ckad-wn0 \
    --cpus 2 \
    --memory 8G \
    --disk 20G \
    --network name=br0,mode=auto,mac=52:54:00:ab:cd:02

3. Optimizing Network Configuration

To ensure Kubernetes uses the correct network interface, we need to adjust the interface priorities on each node. Here's a quick way to do it using yq:

# Install yq
sudo wget https://github.com/mikefarah/yq/releases/latest/download/yq_linux_amd64 -O /usr/bin/yq \
&& sudo chmod +x /usr/bin/yq

# Update netplan configuration
sudo cp /etc/netplan/50-cloud-init.yaml /etc/netplan/50-cloud-init.yaml.old
sudo yq '.network.ethernets.default.match.macaddress as $default | 
        .network.ethernets.extra0.match.macaddress as $extra | 
        .network.ethernets.default.match.macaddress = $extra | 
        .network.ethernets.extra0.match.macaddress = $default' \
    /etc/netplan/50-cloud-init.yaml.old | 
    sudo tee /etc/netplan/50-cloud-init.yaml

# Restart the node
sudo reboot

Troubleshooting Guide

Common Issues and Solutions

Bridge Network Not Coming Up

   # Check bridge status
   ip link show br0
   # If DOWN, try:
   sudo ip link set br0 up

VMs Can't Reach Internet
- Verify IP forwarding:
```
 sysctl net.ipv4.ip_forward
```

Check iptables rules:
```
 sudo iptables -L -v -n
```
Verify DNS resolution:
```
 dig @8.8.8.8 google.com
```

DHCP Not Working on Bridge
- Check systemd-networkd logs:
```
 journalctl -u systemd-networkd
```

Verify bridge configuration:
```
 networkctl status br0
```

VM Network Priority Issues
- Verify interface metrics:
```
 ip route show
```

Check netplan configuration:
```
 cat /etc/netplan/50-cloud-init.yaml
```

Verification Steps

After setup, verify your environment:

Network Connectivity

   # From VMs
   ping 172.19.180.254  # Should reach bridge
   ping 8.8.8.8         # Should reach internet

Interface Priority

   # Should show bridge interface as priority
   ip route | grep default

DNS Resolution

   # Should resolve correctly
   nslookup kubernetes.io

Performance Optimization Tips

VM Resource Allocation
- Don't overcommit CPU cores
- Leave at least 4GB RAM for host system
- Use SSD for VM storage when possible
Network Performance
- Enable jumbo frames if your network supports it:
```
 sudo ip link set br0 mtu 9000
```

Adjust network buffer sizes:

 sudo sysctl -w net.core.rmem_max=16777216
 sudo sysctl -w net.core.wmem_max=16777216

Conclusion

With this setup, you now have a robust local environment for CKAD preparation. The bridge network configuration ensures reliable communication between nodes, while Multipass provides easy VM management. This environment strikes a balance between functionality and resource efficiency, making it perfect for learning Kubernetes administration.

Remember to monitor system resources during heavy testing, and consider adjusting VM resources based on your workload requirements. While this setup requires more initial configuration than cloud-based alternatives, it provides valuable hands-on experience with networking and system administration concepts that will serve you well in your Kubernetes journey.

Next steps would be to install Kubernetes components and configure your cluster following the provided documentation by the course.

Happy practicing!

Additional Resources

How to sync your Obsidian vault using GitHub: A complete guide

Patricio Díaz — Fri, 01 Nov 2024 02:44:56 +0000

Introduction

Obsidian has become a powerful tool for note-taking and personal knowledge management, but one question often comes up: "How can I sync my notes across devices?" While Obsidian offers a paid sync service, there's a robust alternative using GitHub that's both free and secure. In this guide, I'll walk you through setting up GitHub synchronization for your Obsidian vault, whether you're on desktop or mobile.

Prerequisites

Before we begin, you'll need:

An Obsidian installation
A GitHub account
Basic familiarity with Git concepts (though I'll explain the essential commands)

Setting Up Your GitHub Repository

Create a private GitHub repository to store your notes
Generate a personal access token:
- Navigate to GitHub Settings → Developer Settings → Personal access tokens → Fine-grained tokens
- Set the following permissions:
  - Read access to metadata
  - Read and Write access to code and commit statuses

Pro Tip: While classic tokens work too, fine-grained tokens offer better security through more precise permission control.

Creating Your Obsidian Vault

To ensure a smooth setup, we'll start fresh:

Create a new vault in Obsidian
Choose your preferred name and location
Remove any default files (like Welcome.md)

Installing and Configuring the Git Plugin

Enable community plugins in Obsidian:
- Go to Vault's setup → Community plugins
- Toggle "Turn on community plugins"
Install the Git plugin by Vinzent:
- Navigate to Browse → search for "Git"
- Install and enable the plugin

Don't worry if you see a message about not finding a valid Git repository—that's expected at this stage.

Repository Setup Methods

Mobile Setup

Mobile devices use a JavaScript implementation of Git called isomorphic-git, making the setup process slightly different:

In Git plugin settings, scroll to Authentication/commit author
Enter your GitHub username
Paste your personal access token
Use the command palette to find "git clone an existing remote repo"
Enter your repository's HTTPS URL
Select "Vault Root" as the clone directory
Choose "NO" when asked about existing .obsidian directory

Desktop Setup

For desktop users, you can use terminal commands for a more traditional Git setup:

cd your/vault/folder
rm *
git init
git branch -m master
git remote add origin https://<your-personal-token>@github.com/username/repo.git
git pull origin master

Important: Managing .gitignore

To prevent synchronization conflicts, create a .gitignore file with these entries:

.obsidian
.trash
.vscode
conflict-files-obsidian-git.md

On mobile, use the "git edit .gitignore" command from the palette to add these entries.

Daily Synchronization Workflow

Once everything is set up, syncing becomes straightforward:

Open Git source control (via UI or command palette)
Stage changed files using the + icon
Commit changes with the check icon
Push changes using the upload icon
Pull updates using the download icon
For convenience, there's a "Commit-and-sync" button that combines staging, committing, and syncing into one action.

Conclusion

Setting up GitHub synchronization for Obsidian might seem daunting at first, but it offers a powerful and free way to keep your notes in sync across devices. This setup not only provides version control for your notes but also gives you complete control over your data. With the workflow established here, you can focus on what matters most: capturing and developing your ideas in Obsidian while maintaining a reliable backup of your knowledge base.
Remember to regularly sync your changes and keep your access token secure. Happy note-taking!

From Pi to Sky: How My Kubernetes Cluster Evolved Beyond Raspberry

Patricio Díaz — Wed, 18 Sep 2024 00:53:10 +0000

Ever embarked on a project that seemed straightforward at first, only to find yourself tumbling down a rabbit hole of challenges and discoveries? That's exactly what happened when I decided to breathe new life into my ageing Kubernetes cluster. What began as a simple upgrade turned into an odyssey through the world of single-board computers, operating systems, and DIY ingenuity.
It all started a few years ago with a Raspberry Pi 2, four Raspberry Pi Zeros, and a cluster hat from 8086.net. Little did I know that this modest setup would lead me on a journey spanning multiple hardware platforms, wrestling with ARM architectures, and ultimately crafting my own solutions to keep my cluster alive and kicking.
In this post, I'll take you through the twists and turns of my cluster resurrection project. From the initial roadblocks of discontinued support to the thrill of discovering alternative hardware, and finally, to the satisfaction of creating custom solutions. Whether you're a fellow tinkerer, a Kubernetes enthusiast, or simply curious about the world of single-board computing, buckle up – this tale of perseverance and problem-solving might just inspire your next tech adventure.

A bit of history

The Initial Setup

It all began a few years ago when I stumbled upon the cluster hats from 8086.net. Intrigued by the possibility of creating my own Kubernetes cluster, I decided to take the plunge. That old Raspberry Pi 2 Model B that had been gathering dust in a drawer finally would have a purpose!
For the cluster nodes, there's nothing to think about, just got some Raspberry Pi Zeros. Little did I know that acquiring these tiny powerhouses would be my first hurdle. Due to their popularity and supply constraints, most suppliers had implemented a strict one-per-customer limit. Undeterred, I embarked on a quest that led me to four different suppliers just to obtain the necessary quartet of Zeros.

With all the hardware in hand, I assembled my cluster. The Raspberry Pi 2 served as the controller, while the four Zeros, neatly arranged on the cluster hats, formed the nodes. I opted for K3s, a lightweight Kubernetes distribution perfect for my modest hardware. For a while, everything hummed along smoothly. My little cluster was up and running, handling tasks and teaching me the ins and outs of Kubernetes management.

The Fall of 32-bit and the Quest for Alternatives

The bliss was short-lived. As technology marched forward, K8s and K3s made the decision to drop support for ARM 32-bit architectures. Suddenly, my trusty Raspberry Pi Zeros were obsolete for this purpose. I found myself at a crossroads – should I abandon the project or find a way to adapt?
My first instinct was to look at the Raspberry Pi Zero 2 W, a 64-bit capable successor. However, I quickly ran into familiar problems: high prices and purchase limits. It was déjà vu all over again.

Enter the Banana Pi

In my search for alternatives, I stumbled upon the Banana Pi M2 Zero. These boards were not only drop-in replacements with the same form factor and pinout as the Pi Zeros, but they also sported 64-bit processors. Best of all, they were significantly cheaper and had no quantity limitations.

Thanks to a helpful thread on the Cluster Hat's Google Groups page, I found pre-built images and enough information to get the Banana Pis up and running as nodes. My cluster was back in business, now with 64-bit capable nodes.

The Final Evolution: Orange Pi CM4

Recently, I decided it was time for the controller board to join the 64-bit party. In the spirit of exploration (and, admittedly, for the fun of it), I opted for an Orange Pi CM4 with a base board to replace the ageing Raspberry Pi 2. The form factor and pinout matched, making it a perfect candidate.
However, this final upgrade proved to be the most challenging. There were no pre-built images for using the Orange Pi as a controller with the cluster hat. I found myself diving deep into the differences between Raspbian/Raspberry Pi OS and the various operating systems available for the Orange Pi.

The Home Stretch: Custom Solutions

Over the next couple of weeks, I immersed myself in learning the intricacies of operating systems for Orange Pi and Banana Pi. I spent countless hours refactoring and updating the original scripts provided by Cluster Hat. It was a journey of discovery, frustration, and ultimately, triumph.
The result of this labor was the creation of two GitHub repositories containing scripts to smoothly create images for both the Orange Pi CM4 controller and the Banana Pi M2 Zero nodes. What started as a simple cluster project had evolved into a deep dive into single-board computing, operating systems, and custom software solutions.

Hands on!

Controller board

The main components used on the controller board:

Orange Pi CM4 4G32G+CM4 Base Board: RK3566 CPU, 4G DDR4 RAM, 32G eMMC on-board storage
A 128G 2242 M.2 NVME PCIe 3.0x4 SSD card (optional, I plan to use it for PVC provisioning on Kubernetes)
3.5mm pitch screw terminal. For independently powering the hat, see here

Get the images

From the repo

Download the images from the releases page on the repo and skip to the Burn it section below

Build them yourself

You might want to fine-tune or customize the images.

# clone the repo
$ git clone git@github.com:padiazg/clusterhat-orangepi-cm4.git
$ cd clusterhat-orangepi-cm4

# create the required folders
$ mkdir -p build/dest build/img build/mnt

Download a base image from here into the build/img folder, I use the Ubuntu Jammy server image as it was the most updated and flawless from the options available.

I don't provide a shell example for it as there's no way, I think, to download a Google Drive file straightforwardly with wget or curl

Time to create the images

$ cd build

# you need sudo because of losetup and mount used in the scripts
$ sudo ./create.sh Orangepicm4_1.0.6

# once the script has finished the images should be in build/dest
$ ls -l dest

Burn it

Burn the image into an SD card by using any method you're comfortable with: Raspberry Pi Imager, Balena Etcher, dd

# list the block storages to find your SD
$ lsblk
AME          MAJ:MIN RM   SIZE RO TYPE  MOUNTPOINTS
sda             8:0    0 698,6G  0 disk  
└─sda1          8:1    0 698,6G  0 part  /home/pato/vaults/backup
sdb             8:16   0 931,5G  0 disk  
└─sdb1          8:17   0 931,5G  0 part  /home/pato/vaults/mis-cosas
sdc             8:32   1  29,7G  0 disk  
└─sdc1          8:33   1  29,4G  0 part  
zram0         251:0    0    16G  0 disk  [SWAP]
nvme0n1       259:0    0 931,5G  0 disk  
├─nvme0n1p1   259:1    0  1022M  0 part  /boot/efi
├─nvme0n1p2   259:2    0     4G  0 part  /recovery
├─nvme0n1p3   259:3    0 922,5G  0 part  /
└─nvme0n1p4   259:4    0     4G  0 part  
  └─cryptswap 252:0    0     4G  0 crypt [SWAP]


# the SD is at /dev/sdc in this example 
$ sudo umount /dev/sdc 
$ sudo dd bs=1M if=build/dest/Orangepicm4_1.0.6-1-ubuntu_jammy_server_linux5.10.160-ClusterCTRL-CNAT.img of=/dev/sdc status=progress

Boot and access the controller

Place the SD card into the board and power it.
Find out what's the IP address assigned to the board, there are many ways but here's one:

$ sudo nmap -sS 192.168.1.0/24
...
Nmap scan report for pi.hole (192.168.1.100)
Host is up (0.00018s latency).
Not shown: 994 closed ports
PORT     STATE SERVICE
22/tcp   open  ssh
53/tcp   open  domain
80/tcp   open  http
81/tcp   open  hosts2-ns
443/tcp  open  https
8443/tcp open  https-alt
MAC Address: DC:A6:32:BB:97:30 (Raspberry Pi Trading)

Nmap scan report for clusterhat-01.local.patodiaz.io (192.168.1.110)
Host is up (0.00045s latency).
Not shown: 995 closed ports
PORT     STATE SERVICE
22/tcp   open  ssh
111/tcp  open  rpcbind
2049/tcp open  nfs
5555/tcp open  freeciv
8000/tcp open  http-alt
MAC Address: 00:00:A4:ED:A7:29 (Acorn Computers Limited)

Nmap scan report for cnat.local (192.168.1.235)
Host is up (0.00056s latency).
Not shown: 995 closed ports
PORT      STATE SERVICE
22/tcp    open  ssh
111/tcp   open  rpcbind
2049/tcp  open  nfs
5555/tcp  open  freeciv
49175/tcp open  unknown
MAC Address: 00:00:A4:FD:FF:FD (Acorn Computers Limited)
...

I leverage Pi-hole's DHCP capabilities to implement MAC address-based static IP assignment for key devices within my local network. This approach allows for consistent addressing of critical nodes. Furthermore, I utilize Pi-hole's local DNS functionality to pair each of these static IP addresses with a corresponding domain name, facilitating easier identification and access to these devices across the network.

You should be able to access the controller now. The default username and password is "pi:clusterctrl"

$ ssh pi@192.168.1.213

Boot from eMMC

You might also want to use the eMMC storage, so you don't need a SD card to boot. In such a case, you still need the SD to boot the board and copy the OS to the eMMC. This procedure is described in the manual found here

Create a bootable SD. Use any base image, or those you created or downloaded from the repo, as long as it can boot the board.
Copy the image to the SD

# mount the SD card to copy the image
$ mount /dev/sdc /mnt/p2

$ cp dest/Orangepicm4_1.0.6-1-ubuntu_jammy_server_linux5.10.160-ClusterCTRL-CNAT.img /mnt/p2/home/your_user

Boot the board with the SD, then copy the image to the eMMC

# identify the eMMC device
$ ls /dev/mmcblk*boot0 | cut -c1-12**
/dev/mmcblk0

# clear the device, use the device from the prior step
$ sudo dd bs=1M if=/dev/zero of=/dev/mmcblk0 count=5000 status=progress

# copy the image
$ sudo dd bs=1M \
    if=Orangepicm4_1.0.6-1-ubuntu_jammy_server_linux5.10.160-ClusterCTRL-CNAT.img \
    of=/dev/mmcblk0 \
    status=progress

# reboot
$ sync && reboot

Unplug the SD to allow the board to boot from the eMMC.

The nodes

As nodes, I'm using four Banana Pi M2 Zero. The reasons are that they are cheap, the CPU has four 64-bit cores, and there's no restriction on how many I can buy at once, amongst other improvements you can check on their wiki
The instructions for creating the images are pretty much the same as those for the controller, so I'll try not to make it longer.

Get the images

From the repo

Download the images from the releases page on the repo and skip to the Burn it section below

Build them yourself

# clone the repo
$ git clone git@github.com:padiazg/clusterhat-orangepi-cm4.git
$ cd clusterhat-orangepi-cm4

# create the required folders
$ mkdir -p build/dest build/img build/mnt

To get a base image for the BPi M2 Zero that works well with the cluster hat is a bit trickier, mostly because of kernel support for usb-otg which is fundamental for the nodes.
Download the Debian Bullseye base image from here into the build/img folder, here's a direct link. This one works as expected, and is the most updated I could successfully make it work.

I use a custom setting to create images prepared to work with a CNAT controller because it is what I use in my infra. I'll explain later the differences between using a CNAT and a CBRIDGE controller.

I create a config-local.sh file next to the config.sh file

#!/bin/sh
UPGRADE=1
GROWLITE="2G"
CNAT_IMAGES=1

Now create the images

$ cd build

$ sudo ./create.sh Armbian_22.08.0  

# the images should be in build/dest
$ ls -l dest

Burn it

# list the block storages to find your SD
$ lsblk

# SD is at /dev/sdc for this example 
$ sudo umount /dev/sdc 
$ sudo dd bs=1M if=build/dest/Armbian_22.08.0-1-trunk_Bananapim2zero_bullseye_current_5.15.43-ClusterCTRL-p1-CNAT.img of=/dev/sdc status=progress

Boot and access the node

Place the SD card into the node. To start the node we need to use the clusterctrl tool.
Please read the cluster-hat control page to get familiarized with the basic tasks

At the controller

# get some info about the cluster-hat
$ clusterctrl status

# start the P1 node
$ clusterctrl on p1

# stop the P1 node
$ clusterctrl off p1

Let's explain a bit the networking

## the network interfaces
$ ip link
1: lo: <LOOPBACK,UP,LOWER_UP> mtu 65536 qdisc noqueue state UNKNOWN mode DEFAULT group default qlen 1000
    link/loopback 00:00:00:00:00:00 brd 00:00:00:00:00:00
2: eth0: <BROADCAST,MULTICAST,UP,LOWER_UP> mtu 1500 qdisc mq state UP mode DEFAULT group default qlen 1000
    link/ether 00:00:a4:ed:a7:29 brd ff:ff:ff:ff:ff:ff
6: wlan0: <BROADCAST,MULTICAST> mtu 1500 qdisc noop state DOWN mode DEFAULT group default qlen 1000
    link/ether 54:78:c9:0d:8c:34 brd ff:ff:ff:ff:ff:ff
7: brint: <NO-CARRIER,BROADCAST,MULTICAST,UP> mtu 1500 qdisc noqueue state DOWN mode DEFAULT group default qlen 1000
    link/ether ce:90:04:cf:0c:74 brd ff:ff:ff:ff:ff:ff
11: br0: <BROADCAST,MULTICAST,UP,LOWER_UP> mtu 1500 qdisc noqueue state UP mode DEFAULT group default qlen 1000
    link/ether 00:00:a4:ed:a7:29 brd ff:ff:ff:ff:ff:ff
39: ethpi2: <BROADCAST,MULTICAST,UP,LOWER_UP> mtu 1500 qdisc fq_codel master br0 state UNKNOWN mode DEFAULT group default qlen 1000
    link/ether 00:22:82:ff:fe:02 brd ff:ff:ff:ff:ff:ff
41: ethpi3: <BROADCAST,MULTICAST,UP,LOWER_UP> mtu 1500 qdisc fq_codel master br0 state UNKNOWN mode DEFAULT group default qlen 1000
    link/ether 00:22:82:ff:fe:03 brd ff:ff:ff:ff:ff:ff
42: ethpi4: <BROADCAST,MULTICAST,UP,LOWER_UP> mtu 1500 qdisc fq_codel master br0 state UNKNOWN mode DEFAULT group default qlen 1000
    link/ether 00:22:82:ff:fe:04 brd ff:ff:ff:ff:ff:ff
...

# the addresses assigned to each one
$ ip a
1: lo: <LOOPBACK,UP,LOWER_UP> mtu 65536 qdisc noqueue state UNKNOWN group default qlen 1000
    link/loopback 00:00:00:00:00:00 brd 00:00:00:00:00:00
    inet 127.0.0.1/8 scope host lo
       valid_lft forever preferred_lft forever
    inet6 ::1/128 scope host 
       valid_lft forever preferred_lft forever
2: eth0: <BROADCAST,MULTICAST,UP,LOWER_UP> mtu 1500 qdisc mq state UP group default qlen 1000
    link/ether 00:00:a4:ed:a7:29 brd ff:ff:ff:ff:ff:ff
    inet 192.168.1.110/24 brd 192.168.1.255 scope global dynamic eth0
       valid_lft 80240sec preferred_lft 80240sec
    inet6 fe80::200:a4ff:feed:a729/64 scope link 
       valid_lft forever preferred_lft forever
3: brint: <NO-CARRIER,BROADCAST,MULTICAST,UP> mtu 1500 qdisc noqueue state DOWN group default qlen 1000
    link/ether ce:90:04:cf:0c:74 brd ff:ff:ff:ff:ff:ff
    inet 172.19.180.254/24 brd 172.19.180.255 scope global brint
       valid_lft forever preferred_lft forever
4: br0: <BROADCAST,MULTICAST,UP,LOWER_UP> mtu 1500 qdisc noqueue state UP group default qlen 1000
    link/ether 00:00:a4:ed:a7:29 brd ff:ff:ff:ff:ff:ff
    inet 172.19.181.254/24 brd 172.19.181.255 scope global br0
       valid_lft forever preferred_lft forever
    inet6 fe80::200:a4ff:feed:a729/64 scope link 
       valid_lft forever preferred_lft forever
5: ethpi1: <BROADCAST,MULTICAST,UP,LOWER_UP> mtu 1500 qdisc fq_codel master br0 state UNKNOWN group default qlen 1000
    link/ether 00:22:82:ff:fe:01 brd ff:ff:ff:ff:ff:ff
    inet6 fe80::222:82ff:feff:fe01/64 scope link 
       valid_lft forever preferred_lft forever
6: ethpi2: <BROADCAST,MULTICAST,UP,LOWER_UP> mtu 1500 qdisc fq_codel master br0 state UNKNOWN group default qlen 1000
    link/ether 00:22:82:ff:fe:02 brd ff:ff:ff:ff:ff:ff
    inet6 fe80::222:82ff:feff:fe02/64 scope link 
       valid_lft forever preferred_lft forever
7: ethpi3: <BROADCAST,MULTICAST,UP,LOWER_UP> mtu 1500 qdisc fq_codel master br0 state UNKNOWN group default qlen 1000
    link/ether 00:22:82:ff:fe:03 brd ff:ff:ff:ff:ff:ff
    inet6 fe80::222:82ff:feff:fe03/64 scope link 
       valid_lft forever preferred_lft forever
8: ethpi4: <BROADCAST,MULTICAST,UP,LOWER_UP> mtu 1500 qdisc fq_codel master br0 state UNKNOWN group default qlen 1000
    link/ether 00:22:82:ff:fe:04 brd ff:ff:ff:ff:ff:ff
    inet6 fe80::222:82ff:feff:fe04/64 scope link 
       valid_lft forever preferred_lft forever
...

The ethpix interfaces are added to the br0 bridge, they share the 171.19.181.0/24 network:

# the controller
$ ping 172.19.181.254

# the P1 node
$ ping 172.19.181.1

# the P2 node
$ ping 172.19.181.2

# the P3 node
$ ping 172.19.181.3

# the P4 node
$ ping 172.19.181.4

Worth mentioning that the mac-addresses of each node follow the pattern 00:22:82:ff:fe:0x where x is a number between 1 and 4 matching the node number. This is very useful when assigning IP addresses based on the mac-addresses, especially if we are in a CBRIDGE configuration.

You should be able to ssh any of the nodes using the info above

$ ssh pi@172.19.181.1 # P1
$ ssh pi@172.19.181.2 # P2
# and so on

Difference between CBRIDGE and CNAT

The main difference between the two is how nodes get an IP address, and how the cluster components access the network.
At both configurations the br0 network is configured and each node is assigned the internal ip addresses as mentioned before, but the main difference is how the traffic is routed to the rest of the network and other networks like the internet.

In a CBRIDGE configuration the nodes get bridged through the controller network and access the network directly. Each node will get an ip address either manually or via an DHCP present in the network, as if it is a device directly connected to the network.
In the other hand, in a CNAT configuration, the nodes traffic is nated and the controller acts as a router hiding the nodes from the outside.

Conclusion: Lessons Learned and the Road Ahead

As I sit back and reflect on this journey, from those first Raspberry Pi Zeros to the current setup with Banana Pi nodes and an Orange Pi controller, I'm struck by how much I've learned and how far this project has come.
What started as a simple desire to build a Kubernetes cluster became a crash course in hardware compatibility, operating system intricacies, and the importance of community knowledge. Each obstacle - from supply constraints to architecture changes - pushed me to think creatively and expand my skillset.
Perhaps the most valuable lesson was the reminder that in the world of technology, change is the only constant. The ability to adapt, whether it's finding alternative hardware or writing custom scripts, is crucial. This project also reinforced the power of open-source communities. Without the shared knowledge and pre-built images from other enthusiasts, many of the hurdles would have been much harder to overcome.
The two GitHub repositories I've created for image creation are not just the end result of this project, but also my contribution back to the community that helped me along the way. I hope that other tinkerers and cluster enthusiasts will find them useful in their own journeys.
Looking ahead, I'm excited about the possibilities this upgraded cluster opens up. With more powerful, 64-bit capable nodes and a controller, I can explore more complex Kubernetes deployments and perhaps even venture into edge computing scenarios. By the way, I already have two Orange Pi Zero 2W with 2GB RAM each, even more powerful than the Banana Pi M2 Zero,and also just saw there are some Radxa ZERO 3W with 4G of RAM, both of them bringing new challenges to this project.
This project may have started with a handful of Pis and a dream, but it's grown into so much more. It's a testament to the joy of problem-solving, the power of perseverance, and the endless possibilities when you're willing to think outside the (Raspberry Pi) box.
So, what's next? Who knows - but I'm certain it will involve more tinkering, learning, and pushing the boundaries of what's possible with these amazing single-board computers. The sky's the limit!

DEV Community: Patricio Díaz

Numerical Root-Finding Algorithms: Foundations, Theory, and Advanced Methods. Part 1

1. Introduction to Root-Finding Problems

2. Fundamental Algorithms Comparison

2.1 Bisection Method

Mathematical Principles

Convergence Characteristics

Pros and Cons

2.2 Newton-Raphson Method

Mathematical Derivation

Convergence Speed

Computational Complexity

Pros and Cons

3. Advanced Root-Finding Algorithms

3.1 Secant Method

Mathematical Principles

Convergence Speed

Pros and Cons

3.2 Brent’s Method

Mathematical Principles

Convergence Speed

Pros and Cons

4. Real-World Applications of Root-Finding Methods

Engineering and Physics: Solving Nonlinear Equations

Computer Graphics: Ray Tracing and Geometric Calculations

Economics: Solving Market Equilibrium Problems

5. Choosing the Right Method: Linear vs. Quadratic Convergence

Bisection Method: Guaranteed Convergence but Slow

Newton-Raphson Method: Rapid Convergence for Smooth Functions

When to Choose Which Method

- When dealing with smooth, well-behaved functions that allow for reliable derivative computation.

Conclusion

Setting up a local Kubernetes environment with Multipass and bridge networking

Introduction

Why Local Setup?

Hardware Requirements

System Compatibility

Network Architecture

Setting Up the Network Bridge

1. Preparing the Network Environment

2. Configuring the Bridge

3. Enabling IP Forwarding

Optional: Make it permanent

Creating Virtual Machines with Multipass

1. Setting Up Multipass with LXD

2. Launching Kubernetes Nodes

3. Optimizing Network Configuration

Troubleshooting Guide

Common Issues and Solutions

Verification Steps

Performance Optimization Tips

Conclusion

Additional Resources

How to sync your Obsidian vault using GitHub: A complete guide

Introduction

Prerequisites

Setting Up Your GitHub Repository

Creating Your Obsidian Vault

Installing and Configuring the Git Plugin

Repository Setup Methods

Mobile Setup

Desktop Setup

Important: Managing .gitignore

Daily Synchronization Workflow

Conclusion

From Pi to Sky: How My Kubernetes Cluster Evolved Beyond Raspberry

A bit of history

The Initial Setup

The Fall of 32-bit and the Quest for Alternatives

Enter the Banana Pi

The Final Evolution: Orange Pi CM4

The Home Stretch: Custom Solutions

Hands on!

Controller board

Get the images

From the repo

Build them yourself

Burn it

Boot and access the controller

Boot from eMMC