問題タブ [approximation]

ステップサイズが劇的に異なり、データが少ない。>--4-6----3-9----4-7----9-3----4-1---->（ここにステップがあります）のようなデータ-があり、実際にはこのデータは円でループしています。このようなデータの補間に役立つ多項式/式は何ですか？ベジェは機能しますか？

私は現在、高速な TSP 解決 (2 秒で約 50 ～ 100 ノード) を必要とするプロジェクトを行っています。近似アルゴリズムはたくさんありますが、それらを分析して自分でコーディングする時間も意志もありません。

TSP の問題を解決できる無料のライブラリはありますか (概算でも問題ありません)。のようなものsortedNodes = solveTspPrettyPlease(nodes, 2sec)は素晴らしいでしょう。

前もって感謝します。

近似関数としてのニューラル ネットワークの効率をテストしようとしています。

近似する必要がある関数には 5 つの入力と 1 つの出力がありますが、どの構造を使用すればよいですか?

隠しレイヤーの数と各レイヤーのノードの数を決定するために、どの基準を適用する必要があるかわかりません。

よろしくお願いします。

ジュゼッペ。

Greetings. I'm trying to approximate the function

Log10[x^k0 + k1], where .21 < k0 < 21, 0 < k1 < ~2000, and x is integer < 2^14.

k0 & k1 are constant. For practical purposes, you can assume k0 = 2.12, k1 = 2660. The desired accuracy is 5*10^-4 relative error.

This function is virtually identical to Log[x], except near 0, where it differs a lot.

I already have came up with a SIMD implementation that is ~1.15x faster than a simple lookup table, but would like to improve it if possible, which I think is very hard due to lack of efficient instructions.

My SIMD implementation uses 16bit fixed point arithmetic to evaluate a 3rd degree polynomial (I use least squares fit). The polynomial uses different coefficients for different input ranges. There are 8 ranges, and range i spans (64)2^i to (64)2^(i + 1). The rational behind this is the derivatives of Log[x] drop rapidly with x, meaning a polynomial will fit it more accurately since polynomials are an exact fit for functions that have a derivative of 0 beyond a certain order.

SIMD table lookups are done very efficiently with a single _mm_shuffle_epi8(). I use SSE's float to int conversion to get the exponent and significand used for the fixed point approximation. I also software pipelined the loop to get ~1.25x speedup, so further code optimizations are probably unlikely.

What I'm asking is if there's a more efficient approximation at a higher level? For example:

1. Can this function be decomposed into functions with a limited domain like log2((2^x) * significand) = x + log2(significand)

hence eliminating the need to deal with different ranges (table lookups). The main problem I think is adding the k1 term kills all those nice log properties that we know and love, making it not possible. Or is it?

1. Iterative method? don't think so because the Newton method for log[x] is already a complicated expression

2. Exploiting locality of neighboring pixels? - if the range of the 8 inputs fall in the same approximation range, then I can look up a single coefficient, instead of looking up separate coefficients for each element. Thus, I can use this as a fast common case, and use a slower, general code path when it isn't. But for my data, the range needs to be ~2000 before this property hold 70% of the time, which doesn't seem to make this method competitive.

Please, give me some opinion, especially if you're an applied mathematician, even if you say it can't be done. Thanks.

ランダム グラフの dfs ツリーの葉を削除した後、残ったエッジの数が |S| であると仮定すると、そのグラフのマッチングが |S|/2 になることを証明できますか?

Vertex-Cover 問題 (VC、既知の Np-Complete 問題) の 2 近似アルゴリズムに関する質問を見たことがありますが、答えがわかりません。問題は次のとおりです。「スパニング ツリー」を使用して、頂点カバー問題の 2 近似アルゴリズムを見つけます。さて、VC に関しては既に多くの貪欲なアプローチが提示されていますが、「スパニング ツリー」を使用した特殊なアルゴリズムは挑戦的です。何か案が？

4Dベクトルを正規化しようとしています。

私の最初のアプローチは、SSE組み込み関数を使用することでした。これは、ベクトル演算に2倍の速度向上をもたらしました。基本的なコードは次のとおりです：（v.v4が入力です）（GCCを使用）（これはすべてインライン化されています）

分解を確認すると、期待通りのようです。そこには大きな問題は見当たりません。

とにかく、それから私は近似を使ってそれを試しました:(私はグーグルからこれを得ました）

SSEバージョンよりもわずかに高速に実行されています！（約5〜10％高速）結果も非常に正確です-長さを見つけるときは0.001と言います！ しかし..GCCは、型のパンニングのために、その不完全な厳密なエイリアシング規則を私に与えています。

だから私はそれを変更します：

そして今、修正されたバージョン（警告なし）は遅くなっています!! SSEバージョンの実行速度のほぼ60％を実行しています（ただし、同じ結果です）。どうしてこれなの？

だからここに質問があります：

1. 私のSSEインペンションは正しいですか？
2. SSEは通常のfpu操作よりも本当に遅いですか？
3. なぜ3番目のコードはそれほど遅いのですか？

こんにちは、シフトと加算/減算のみを使用して符号なし定数で除算しようとしています-乗算であれば問題ありませんが、除算に少し困惑しています。

たとえば、定数除数が 192 で、被除数が 8000 であるとします。

「完全な結果」 y = 8000/192 = 41 (小数ビットを保持していないと仮定)

y = 8000 >> 8 ... 31 y = 8000 >> 7 ... 62

しかし、どうすればより正確な解を得ることができるでしょうか?

どうもありがとう！

数値オプティマイザーの中間ステップとして、N 個の線形方程式系を解く必要があります。私の知る限り、正確にそうするための合理的に単純なアルゴリズムはO(N ^ 3)です(ただし、O(N ^ 2.8)のような巨大な定数でそれを行うことができる数学論文で恐ろしく複雑なものを見ました)。場合によっては、N が巨大になることがあります。つまり、数千です。

O(N^3) 未満で一次方程式系のまともな近似解を得る良い方法はありますか?

編集：

それがまったく役立つ場合、ここにいくつかの詳細があります。

1. 私の行列は対称であり、疎ではありません。

2. これは、ニュートン ラフソンの 2 次導関数行列です。2000 次元の空間で何かを最適化しようとしています。

与えられた精度 (0.0001 など) で (1-x)^0.25 を近似する必要があります。ウィキペディアにある (1+x)^0.25 の展開を使用しています。現在の式が精度よりも低い場合、近似を停止する必要があります。

long double n は気にしないでください。:P これは、現在の式の値をチェックしているのではなく、1000 以上の式を計算しているときにうまく機能します。関数の定義域は <-1;1> で、s() は <-1;~0.6> で x の近似をうまく計算します。引数が大きいほど計算誤差が大きくなります。0.6からは精度を超えています。

私は英語の数学言語をよく知らないので、問題が十分に明確かどうかわかりません. 問題は、 while 条件の問題と、関数 s() が正しく近似されない理由です。

編集： 問題はほとんど解決しました。x>0 の場合、連続する式の絶対値を 1 から引く必要があります。

その後、精度は大幅に向上します (もちろん fox x>0)。重複エラーは、長い double 不正確性に起因します。それで全部です。とにかくあなたたちに感謝します。