performance - Product of two Toeplitz matrices? -

-

the o(n log n) algorithm product of toeplitz matrix , vector of correct length well-known: put in circulant matrix, multiply vector (and subsequent zeroes), , return top n elements of product.

i'm finding trouble finding best (time-wise) algorithm multiplying 2 toeplitz matrices of same size.

can give me algorithm this?

here's o(n^2)-time algorithm.

to compute 1 of diagonals of product matrix, need compute dot products on length-n windows of length-(2n-1) lists sliding in lockstep. difference between 2 successive entries can computed in time o(1).

for example, consider product of

e f g h    o p q r s d e f g h    m o p q r c d e f g    l m o p q b c d e f    k l m o p b c d e    j k l m o

the 1,1 entry eo + fm + gl + hk + ij. 2,2 entry dp + eo + fm + gl + hk, or 1,1 entry minus ij plus dp. 3,3 entry cq + dp + eo + fm + gl, or 2,2 entry minus hk plus cq. 4,4 entry br + cq + dp + eo + fm, etc.

if implement in floating point, mindful of catastrophic cancellation.


Comments

Post a Comment

Popular posts from this blog

javascript - Image onload event not firing in firefox -

-
i'm creating image preloader. works fine in browsers except firefox (testing firefox 10.0). input array of images called image_list . these images appended dynamically body of document , load callback attached, calls function update_progress . code follows: $(image_list).each(function() { var x = $('<img />') .load(function() {update_progress(percent_loaded += step);}) .attr('src', this) .appendto('body') .css('display', 'none'); .each(function() { if(this.complete) update_progress(percent_loaded += step); }); }); in firefox, load callback , update_progress never called. yet exact same code works fine in chrome , other browsers i've tested. there way detect when image has loaded in firefox? i first check see whether image has height, checking height property. if (the_image.height > 0) { // image loaded (possibly cached) } if have cached ...
Read more

android - getbluetoothservice() called with no bluetoothmanagercallback -

-
i getting getbluetoothservice() called no bluetoothmanagercallback error in android application. i have no idea causing or bluetooth manager callbacks. can give me idea of causing problem or start looking. by reading android source code, seems warning cannot about. source code shows if call bluetoothsocket#connect(); then call bluetoothadapter.getdefaultadapter().getbluetoothservice(null); the key here, null parameter passes in above line. due this, there no callback, , bluetoothsocket class throw out warning. since warning, not think need it. https://android.googlesource.com/platform/frameworks/base/+/master/core/java/android/bluetooth/bluetoothsocket.java line 306 https://android.googlesource.com/platform/frameworks/base/+/master/core/java/android/bluetooth/bluetoothadapter.java line 1610
Read more

sql - ASP.NET SqlDataSource, like on SelectCommand -

-
i'm working on asp.net. have sqldatasource query hardcoded on selectcommand: <asp:sqldatasource id="datasource1" runat="server" cancelselectonnullparameter="false" connectionstring="<%$ connectionstrings:s.properties.settings.connectionstring %>" selectcommand="select * [table] ([col1] case @col1_param when null col1 else @col1_param end) , ([col2] case @col2_param when null col2 else @col2_param end)" selectcommandtype="text"> <selectparameters> <asp:controlparameter controlid="textbox1" name="col1_param" propertyname="text" type="string" /> <asp:controlparameter controlid="textbox2" name="col2_param" propertyname="text" type="string" /> </selectparameters> what want if enter data on 1 textbox only, data display according textbox...
Read more