Metric and Probability-Based Recommendations

How many of you like to eat, play, and most importantly, drink? (Hopefully, everyone!)

I helped create an app called LocALL. It gives 50,000 recommendations for short trips to eat, play, and drink and support local businesses in Austin. We can extend our app to cover ~400 metropolitan cities in the US and create 20 million recommendations. (Big data and machine learning!)

At the heart of our solution is math. We used spherical geometry and probability to create simple, fast recommendations.

Continue reading “Metric and Probability-Based Recommendations”

Advertisements

Iterative Methods: Part 3

Let’s look at one more way to solve the equation A\vec{x} = \vec{b}. We assume that A \in \mathbb{R}^{n \times n} is nonsingular, and define the k-th Krylov subspace as follows:

\mathscr{K}_{k} \,:=\, \mbox{span}\{\vec{b},\,A\vec{b},\,\cdots,\,A^{k - 1}\vec{b}\}.

Krylov subspace methods are efficient and popular iterative methods for solving large, sparse linear systems. When A is symmetric, positive definite (SPD), i.e.

\left\{\begin{array}{l} A^{T} = A \\[12pt] \vec{x}^{T}A\vec{x} > 0,\,\,\,\forall\,\vec{x} \neq \vec{0}, \end{array}\right.

we can use a Krylov subspace method called Conjugate Gradient (CG).

Today, let’s find out how CG works and use it to solve 2D Poisson’s equation.

Continue reading “Iterative Methods: Part 3”

Iterative Methods: Part 2

Last time, we looked at 2D Poisson’s equation and discussed how to arrive at a matrix equation using the finite difference method. The matrix, which represents the discrete Laplace operator, is sparse, so we can use an iterative method to solve the equation efficiently.

Today, we will look at Jacobi, Gauss-Seidel, Successive Over-Relaxation (SOR), and Symmetric SOR (SSOR), and a couple of related techniques—red-black ordering and Chebyshev acceleration. In addition, we will analyze the convergence of each method for the Poisson’s equation, both analytically and numerically.

Continue reading “Iterative Methods: Part 2”

Iterative Methods: Part 1

Once again, we consider solving the equation A\vec{x} = \vec{b}, where A \in \mathbb{R}^{n \times n} is nonsingular. When we use a factorization method for dense matrices, such as LU, Cholesky, SVD, and QR, we make O(n^{3}) operations and store O(n^{2}) matrix entries. As a result, it’s hard to accurately model a real-life problem by adding more variables.

Luckily, when the matrix is sparse (e.g. because we used finite difference method or finite element method), we can use an iterative method to approximate the solution efficiently. Typically, an iterative method incurs O(n^{2}) operations, if not fewer, and requires O(n) storage.

Over the next few posts, we will look at 5 iterative methods:

  • Jacobi
  • Gauss-Seidel
  • Successive Over-Relaxation (SOR)
  • Symmetric SOR (SSOR)
  • Conjugate Gradient (CG).

In addition, we will solve 2D Poisson’s equation using these methods. We will compare the approximate solutions to the exact to illustrate the accuracy of each method.

Continue reading “Iterative Methods: Part 1”

Isogeometric Analysis Library

Today, I make my Isogeometric Analysis library available to you.

Written in Matlab, it reflects the time and effort that I spent in graduate school. It also shows unfortunate age, as B-splines and NURBS are fully supported, but not T-splines and other basis that are state-of-the-art. One day, I hope to return.

You can find my Isogeometric Analysis library here:
Download from GitHub

If you like regular, vanilla Finite Element Analysis:
Download from GitHub