First, I tested on berlin52. The program occasionally finds the optimal solution, usually taking a few hundred iterations.
Next, I tested a 127-city problem, bier127.tsp. I started with 1,000 initial random routes.
The optimal solution is known to be of length 118282, but the optimal solution found by the program is 121950. This is ~3% above optimal.
| import Accelerate | |
| private let Epsilon: Double = 1e-8 | |
| private enum LUFactorizationResult { | |
| case success(LUFactorization) | |
| case singular(Int) | |
| } | |
| private struct LUFactorization { |
| import numpy as np | |
| from scipy.optimize import linear_sum_assignment, linprog | |
| def main(): | |
| n_verts = 20 | |
| weights = np.random.uniform(low=0.01, high=1.0, size=(n_verts, n_verts)) | |
| print("Using linear programming solution...") | |
| soln = solve_matching_linprog(weights) |
| import numpy as np | |
| from tqdm.auto import tqdm | |
| def is_bitonic(xs): | |
| results = [] | |
| for seq in xs: | |
| prev = seq[0] | |
| direction = 0 | |
| num_changes = 0 | |
| for x1 in seq: |
Benchmarking global reductions with varying numbers of SMs and warps per SM. We find interesting facts, like that using one warp across more SMs is more efficient than more warps across a single SM.
These were computed on an NVIDIA Titan X GPU.
Code for the benchmark is here and the kernel is here.
1 warps
| """ | |
| Compute the closed-form characteristic polynomial of a 4x4 matrix. | |
| """ | |
| import sympy | |
| syms = sympy.symbols('a b c d e f g h i j k l m n o p') | |
| mat = sympy.Matrix([[syms[i+j*4] for i in range(4)] for j in range(4)]) | |
| print(sympy.collect((mat - sympy.eye(4)*sympy.symbols('x')).det(), 'x')) | |
| # a*f*k*p - a*f*l*o - a*g*j*p + a*g*l*n + a*h*j*o - a*h*k*n - b*e*k*p + b*e*l*o + b*g*i*p - b*g*l*m - b*h*i*o + b*h*k*m + c*e*j*p - c*e*l*n - c*f*i*p + c*f*l*m + c*h*i*n - c*h*j*m - d*e*j*o + d*e*k*n + d*f*i*o - d*f*k*m - d*g*i*n + d*g*j*m + x**4 + x**3*(-a - f - k - p) + x**2*(a*f + a*k + a*p - b*e - c*i - d*m + f*k + f*p - g*j - h*n + k*p - l*o) + x*(-a*f*k - a*f*p + a*g*j + a*h*n - a*k*p + a*l*o + b*e*k + b*e*p - b*g*i - b*h*m - c*e*j + c*f*i + c*i*p - c*l*m - d*e*n + d*f*m - d*i*o + d*k*m - f*k*p + f*l*o + g*j*p - g*l*n - h*j*o + h*k*n) |
| import numpy as np | |
| rows = 3 | |
| cols = 6 | |
| # Create all 2^(rows*cols) combinations of egg matrices. | |
| all_combos = np.zeros([1] * (rows * cols + 2), dtype=np.float32) | |
| for i in range(rows * cols): | |
| m = np.zeros([2, rows * cols], dtype=np.float32) | |
| m[1, i] = 1 |
| #!/bin/bash | |
| # | |
| # Center a GNOME window, given its title. All windows with the given title are | |
| # moved to the center of their respective displays. | |
| # | |
| # Example: | |
| # | |
| # bash center_window.sh "foo.png - image editor" | |
| # |
| package main | |
| import ( | |
| "fmt" | |
| "io" | |
| "log" | |
| "os" | |
| "path/filepath" | |
| "github.com/unixpickle/essentials" |